Stack (ngăn xếp) là cấu trúc dữ liệu tuyến tính hoạt động theo cơ chế Last In First Out (LIFO - Vào sau ra trước). Phần tử nào vào trước trong stack sẽ được xử lý sau cùng.
Ví dụ minh họa
Cấu trúc dữ liệu stack có thể hiểu qua ví dụ chồng đĩa.
Các đĩa được chồng lên nhau. Đĩa đầu tiên ở đáy chồng và đĩa đặt sau cùng ở đỉnh chồng. Khi cần đĩa, ta lấy đĩa ở đỉnh chồng - tức đĩa đặt vào cuối cùng. Đĩa đặt đầu tiên sẽ là đĩa được lấy cuối cùng. Do đó, cơ chế LAST IN FIRST OUT được tuân theo.
Triển khai Stack trong Python
Stack trong Python có thể triển khai theo nhiều cách dùng các cấu trúc dữ liệu tuyến tính khác hoặc module built-in trong thư viện Python.
Phương pháp 1 – Triển khai dùng list
Stack trong Python có thể triển khai dùng list. Nhưng dùng list để triển khai stack không hiệu quả lắm và không khuyến khích.
Các phép toán liên quan
append() – Hàm này thêm phần tử vào cuối stack.
pop() – Hàm này xóa và trả về phần tử cuối cùng (đỉnh) trong stack. Hàm này pop các phần tử theo thứ tự LIFO.
Ví dụ
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack ban đầu:", stack)
print("Phần tử pop từ stack:")
print(stack.pop())
print(stack.pop())
print("Stack sau khi pop một vài phần tử:", stack)Kết quả
Stack ban đầu: [1, 2, 3] Phần tử pop từ stack: 3 2 Stack sau khi pop một vài phần tử: [1]
Không thể xóa thêm phần tử khi stack rỗng. Làm vậy sẽ gây exception.
stack.pop() IndexError: pop from empty list
Phương pháp 2 – Triển khai dùng queue.LifoQueue
Đây là cách triển khai stack dùng module built-in của Python. Cần import LifoQueue từ queue. Có thể khởi tạo LifoQueue hoặc stack với kích thước cụ thể. Kích thước 0 nghĩa là stack vô hạn.
Các phép toán liên quan
maxsize – số lượng phần tử tối đa cho phép trong stack
get() – xóa và trả về phần tử cuối (đỉnh) từ stack. Nếu stack rỗng, chờ cho đến khi stack có ít nhất một phần tử.
get_nowait() – xóa và trả về phần tử cuối từ stack. Nếu stack rỗng, ném exception.
put(item) – thêm phần tử vào cuối stack. Nếu stack đầy, chờ cho đến khi có ô trống.
put_nowait(item) – thêm phần tử vào cuối stack. Nếu stack đầy, ném exception.
full() – trả về true nếu stack đầy, ngược lại false.
empty() – trả về True nếu stack rỗng, ngược lại false.
qsize() – trả về số phần tử hiện có trong stack.
Ví dụ
from queue import LifoQueue
s = LifoQueue(maxsize=3)
s.put(1)
s.put(2)
s.put(3)
print("Stack đầy?", s.full())
print("Phần tử pop từ stack:")
print(s.get())
print(s.get())
print("Số phần tử trong stack:", s.qsize())
print("Stack rỗng?", s.empty())Kết quả
Stack đầy? True Phần tử pop từ stack: 3 2 Số phần tử trong stack: 1 Stack rỗng? False
Phương pháp 3: Triển khai dùng collections.deque
Đây là cách khác để triển khai stack trong Python. Cần import deque từ module collections.
Các phép toán liên quan
append() – Hàm này thêm phần tử vào cuối stack.
pop() – Hàm này xóa và trả về phần tử cuối trong stack với độ phức tạp thời gian O(1).
Ví dụ
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack ban đầu:", stack)
print("Phần tử pop từ stack:")
print(stack.pop())
print(stack.pop())
print("Stack sau khi pop một vài phần tử:", stack)Kết quả
Stack ban đầu: deque([1, 2, 3]) Phần tử pop từ stack: 3 2 Stack sau khi pop một vài phần tử: deque([1])
Dùng pop() trên deque rỗng sẽ ném exception.