Trong Ruby hash, array, set, and queue là những gì ta tìm hiểu chủ yếu. Tuy nhiên, Ruby còn cung cấp một số cấu trúc dữ liệu khác phức tạp hơn, biết về các cấu trúc dữ liệu nâng cao hơn cũng giúp mở mang được nhiều kiến thức thú vị. Trong bài viết này mình sẽ giới thiệu về Stacks trong Ruby.
Giới thiệu về Data Structures
Cấu trúc dữ liệu (Data Structures) được sử dụng để lưu trữ và quản lý dữ liệu theo cách hiệu quả và có tổ chức để truy cập và sửa đổi dữ liệu nhanh hơn và dễ dàng. Một số cấu trúc dữ liệu cơ bản là Arrays, LinkedList, Stacks, Queues, v..v..
Giới thiệu về stacks
- Stack (ngăn xếp) là một cấu trúc dữ liệu mà bạn có thể sử dụng nó như là một "to-do" list. Bạn có thể thêm phần tử vào hoặc lấy ra từng phần tử của stack và xử lý, thao tác với chúng tới khi stack rỗng (không còn phần tử nào nữa).
- Ngăn xếp là một loại danh sách liên kết đặc biệt cho phép chúng tôi lưu trữ, truy xuất dữ liệu một cách hiệu quả theo phương pháp nhập sau, xuất trước - LIFO (Last In - First Out). Hay nói cách khác, các phần tử được lấy theo thứ tự ngược lại so với được lưu trữ trên ngăn xếp.
- Cũng như điều đó xảy ra với hàng đợi (queues), các ngăn xếp không cho phép chúng ta chèn / xóa các phần tử tại các vị trí ngẫu nhiên. Và giống như các hàng đợi, chúng không khác gì chuỗi các nút được kết nối.
- Bây giờ, hãy nhìn thấy cách một ngăn xếp phát triển khi chúng ta lưu trữ các phần tử (push)
push(1) push(2) push(3)
--- --- ---
1 2 3
--- --- ---
1 2
--- ---
1
---
- Và cách ngăn xếp thu nhỏ lại khi chúng ta loại bỏ các phần tử (pop)
pop pop pop --- --- --- 3 2 1 --- --- --- 2 1 --- --- 1 ---
- Trái ngược với những gì xảy ra với danh sách liên kết thông thường, khi làm việc với ngăn xếp, bạn không nên sử dụng head và tail trực tiếp từ mã của mình. Cách an toàn nhất để tương tác với ngăn xếp là thông qua các phương thức push, peek and pop.
Dưới đây là các mô tả ngắn gọn về mỗi phương pháp, độ phức tạp và mã nguồn của nó.
Initialize
Phương thức này là constructor stack. Nó tạo ra một ngăn xếp trống, đặt nút head bằng nil và chiều dài ngăn xếp thành 0.
Độ phức tạp của phương thức này là O (1).
def initialize self.head = nil self.length = 0 end
Push
Tạo một nút mới để chèn một giá trị vào ngăn xếp. Nút mới di chuyển phần tử về ở đầu danh sách và trở thành đầu head của danh sách.
Vì ngăn xếp giữ con trỏ đến head và tail của nó, nên độ phức tạp của phương thức này là O (1).
def push data
node = Node.new data
if length == 0
self.tail = node
end
node.next = self.head
self.head = node
self.length += 1
end
Pop
Loại bỏ một yếu tố từ ngăn xếp. Như nó xảy ra với hàng đợi, việc loại bỏ rất đơn giản vì chúng luôn xảy ra ở phần đầu của ngăn xếp.
Để loại bỏ một phần tử khỏi ngăn xếp, chúng ta chỉ head vào nút mà nó bên cạnh nó và đặt đuôi thành 0 nếu ngăn xếp chỉ chứa một phần tử.
Độ phức tạp của phương thức này là O (1).
def pop
return nil unless self.length > 0
self.head = self.head.next
self.tail = nil if self.length == 1
self.length -= 1
end
Peek
Trả về nút mà ở head ngăn xếp mà không loại bỏ nó hoặc không nếu ngăn xếp trống.
Vì pop không trả về phần tử bị loại bỏ, nên peek là cách để đi nếu bạn phải làm gì đó với phần tử đó.
Độ phức tạp của phương thức này là O (1).
def peek self.head end
Clear
Pops tất cả các yếu tố từ ngăn xếp.
Độ phức tạp của phương thức này là O (n).
def clear
while self.peek
pop
end
end
Each
Phương thức này đi qua ngăn xếp năng suất một lần cho đến khi nó đạt đến phần tử cuối cùng.
Độ phức tạp để mang lại mục tiếp theo trong ngăn xếp là O (1). Độ phức tạp để mang lại toàn bộ ngăn xếp là O (n).
def each
return nil unless block_given?
current = self.head
while current
yield current
current = current.next
end
end
In nội dung của ngăn xếp bằng cách đi qua các mục của nó.
Độ phức tạp của phương thức này là O (n).
def print
if self.length == 0
puts "empty"
else
self.each { |node| puts node.data }
end
end
Khi nào nên sử dụng ngăn xếp
Sau khi tìm hiểu về ngăn xếp, mình có thể nói với bạn chắc chắn rằng các ngăn xếp là một trong những cấu trúc dữ liệu được sử dụng nhiều nhất trong lĩnh vực này.
Ngăn xếp rất tốt trong việc quản lý các chuỗi hướng dẫn, phân tích các biểu thức và giải quyết các ưu tiên toán tử.
Kết luận
Trên đây là khái niệm cơ bản về cấu trúc dữ liệu và ngăn xếp. Hi vọng qua khái niệm mình đã trình bày thì các bạn sẽ nắm rõ hơn về ngăn xếp trong Ruby. Làm việc với ngăn xếp có những lợi thế riêng, vì thế mình hi vọng các bạn thích nó!
