Stack (ngăn xếp) là cấu trúc dữ liệu quan trọng với nhiều ứng dụng.
Trong lập trình, stack cho phép lưu trữ dữ liệu theo thứ tự last-in, first-out (LIFO - vào sau ra trước). Nghĩa là mục thêm vào sau cùng sẽ được xử lý đầu tiên.
Làm sao tạo stack trong Python? Đó là câu hỏi hướng dẫn này sẽ trả lời. Cuối bài, bạn sẽ thành thạo tạo và làm việc với stack trong Python.
Stack Python
Stack lưu dữ liệu theo thứ tự LIFO (vào sau ra trước).
Để hiểu cơ chế: hình dung chồng đĩa. Khi rửa đĩa, đĩa đầu tiên bạn lấy là đĩa trên cùng. Rồi lần lượt lấy các đĩa thấp hơn.
Stack ngược với Queue (hàng đợi) trong Python. Queue loại bỏ mục thêm sớm nhất (FIFO - vào trước ra trước), Stack loại bỏ mục thêm gần nhất (LIFO).
Stack thường hỗ trợ 2 thao tác: push (thêm vào đỉnh) và pop (lấy ra đỉnh).
Trong Python, 2 cách chính tạo stack: dùng list tích hợp sẵn và dùng class collections.deque(). Phân tích từng cách.
Dùng List Tích Hợp Sẵn (Built-in List)
Kiểu dữ liệu list built-in cho phép tạo stack trong Python.
Vì Python list triển khai dưới dạng mảng (array), bạn dễ dàng thêm/xóa mục. Thứ tự chèn giá trị được bảo toàn → dễ dàng lấy mục đầu/cuối.
Ví dụ: tạo stack lưu bài tập về nhà. Giáo viên chấm theo thứ tự nộp (nộp sớm ở đáy, nộp muộn ở đỉnh).
Thêm Mục Vào Stack (Push)
Dùng phương thức append() để thêm vào stack. Tạo stack bài tập:
assignments = []
assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
print(assignments)
Kết quả: ['Hannah','Benny','Gordon'].
Code: khai báo list assignments. Dùng append() thêm 3 tên theo thứ tự: Hannah, Benny, Gordon. Gordon nộp sau cùng → ở vị trí cuối list.
Xóa Mục Khỏi Stack (Pop)
Giả sử đã chấm xong bài Gordon, muốn biết bài tiếp theo. Cần xóa mục ở đỉnh stack.
Dùng phương thức pop() để xóa mục đỉnh stack:
assignments = []
assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
assignments.pop()
print(assignments)
Kết quả: ['Hannah','Benny'].
Tên Gordon bị xóa bằng pop(), stack còn Hannah và Benny.
Class collections.deque
Class deque trong thư viện collections cho phép tạo hàng đợi hai đầu (double-ended queue).
Đối tượng deque triển khai dưới dạng danh sách liên kết kép (doubly-linked list) → hiệu năng mạnh và ổn định khi chèn/xóa phần tử. Thêm vào đó, collections thuộc Python Standard Library → import trực tiếp không cần cài thư viện ngoài.
Để dùng collections.deque, import trước:
from collections import deque
Quay lại ví dụ bài tập để minh họa deque.
Thêm Mục Vào Deque Stack
Dùng append() thêm vào deque stack. Tạo hàng đợi bài tập với deque:
from collections import deque
assignments = deque()
assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
print(assignments)
Kết quả: deque(['Hannah','Benny','Gordon']).
Giải thích: Import deque. Tạo deque bằng deque() gán cho assignments. Thêm 3 tên. In nội dung. Kết quả bao bởi deque() vì dùng cấu trúc deque, dù dữ liệu vẫn hoạt động như stack.
Xóa Mục Khỏi Deque Stack
Dùng pop() xóa mục khỏi deque stack.
Giả sử đã chấm xong Gordon và Benny. Xóa chúng khỏi stack:
from collections import deque
assignments = deque()
assignments.append("Hannah")
assignments.append("Benny")
assignments.append("Gordon")
assignments.pop()
assignments.pop()
print(assignments)
Kết quả: deque(['Hannah']).
Code: tạo deque stack 3 giá trị. Chạy pop() 2 lần. Mỗi lần xóa mục đỉnh stack. Gordon rồi Benny bị xóa → chỉ còn Hannah.
Để tìm hiểu thêm về class deque Python, đọc hướng dẫn Python Queues và Deques.
Kết Luận
Stack cho phép lưu trữ dữ liệu theo thứ tự LIFO (vào sau ra trước). Có nhiều cách triển khai stack trong Python, nhưng 2 cách thực tế nhất: dùng cấu trúc list built-in Python, hoặc dùng class collections.deque().
Hướng dẫn này thảo luận, kèm ví dụ, cách tạo stack trong Python dùng list và collections.deque(). Bây giờ bạn đã sẵn sàng tạo stack riêng như lập trình viên Python chuyên nghiệp!