Cấu trúc dữ liệu ngăn xếp (stack) trong Python
Vào sau, ra trước: dùng list làm stack với append, pop và [-1], cấu trúc đứng sau nút hoàn tác và lời gọi hàm.
- push bằng append() và pop bằng pop()
- Xem đỉnh stack bằng [-1]
- Kiểm tra stack rỗng
"third"đã bị popgiá trị vào sau cùng ra trước"second"đỉnh hiện tạistack[-1]"first"đáy
Chỉ chạm được vào đỉnh
Vấn đề
Nút hoàn tác (undo), nút quay lại trong trình duyệt và việc kiểm tra dấu ngoặc có khớp nhau không đều cần ghi nhớ các phần tử và lấy lại phần tử mới nhất trước. Ngăn xếp (stack) là cấu trúc dữ liệu được tạo ra đúng cho việc đó.
Hình dung đời thường
Stack giống chồng đĩa ở căng tin. Đĩa mới đặt lên trên cùng, lấy đĩa cũng lấy từ trên cùng. Đĩa đặt vào sau cùng là đĩa được dùng đầu tiên, và bạn không thể rút một chiếc ở giữa ra.
stack.append("third")🍽️ Đặt một chiếc đĩa lên trênstack.pop()⬆️ Lấy chiếc đĩa trên cùng rastack[-1]👀 Nhìn chiếc đĩa trên cùng mà không lấy rastack📚 Những chiếc đĩa còn trên chồngStack là tập hợp vào sau ra trước (LIFO, last in first out): phần tử chỉ được thêm vào và lấy ra ở đỉnh.
Những điểm quan trọng
stack.append(...)đẩy một phần tử lên đỉnh, tức cuối list.stack.pop()lấy ra và trả về phần tử ở đỉnh, ở đây là"third".stack[-1]đọc phần tử ở đỉnh mà không lấy nó ra.- Cả
appendvàpopđều làm việc ở cuối list, nên rất nhanh.
Khi nào nên sử dụng?
- Lịch sử hoàn tác và làm lại.
- Kiểm tra dấu ngoặc khớp nhau và phân tích biểu thức.
- Tìm kiếm theo chiều sâu và quay lui (backtracking) không cần đệ quy.
Khi nào chưa cần
- Phần tử phải ra theo đúng thứ tự đã vào: đó là hàng đợi (queue).
- Cần lấy phần tử ở giữa hoặc theo vị trí: list thường hoặc cấu trúc khác phù hợp hơn.
Xem cách hoạt động
Push và pop để thấy phần tử vào sau cùng luôn ra trước tiên.
Code ví dụ
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Kết quả khi chạy
popped: third
top: second
stack: ['first', 'second']
Giải thích code
Phương thức append() thêm phần tử vào đỉnh stack, còn pop() lấy ra và xóa phần tử ở đỉnh, nên "third" được lấy ra trước. stack[-1] cho phép xem phần tử trên cùng mà không xóa nó. Cả hai thao tác append() và pop() ở cuối list đều có độ phức tạp trung bình là O(1).
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Lấy ra từ stack rỗng
pop() trên list rỗng gây lỗi IndexError.
item = stack.pop()
if stack:
item = stack.pop()
Dùng đầu list làm đỉnh
insert(0, x) và pop(0) phải dịch chuyển mọi phần tử, nên rất chậm.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Trung bình
- Mini Stack-Language Interpreter Evaluate a small stack language. Khó