Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • push bằng append() và pop bằng pop()
  • Xem đỉnh stack bằng [-1]
  • Kiểm tra stack rỗng
append first, second, third; rồi pop()
  1. "third"đã bị popgiá trị vào sau cùng ra trước
  2. "second"đỉnh hiện tạistack[-1]
  3. "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.

Từ chồng đĩa đến code
stack.append("third")🍽️ Đặt một chiếc đĩa lên trên
stack.pop()⬆️ Lấy chiếc đĩa trên cùng ra
stack[-1]👀 Nhìn chiếc đĩa trên cùng mà không lấy ra
stack📚 Những chiếc đĩa còn trên chồng
Vào sau ra trước: chỉ chạm được vào phần trên cùng.
Định nghĩa ngắn gọn

Stack 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

  1. stack.append(...) đẩy một phần tử lên đỉnh, tức cuối list.
  2. stack.pop() lấy ra và trả về phần tử ở đỉnh, ở đây là "third".
  3. stack[-1] đọc phần tử ở đỉnh mà không lấy nó ra.
  4. Cả append và 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ụ

Chạy code →
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")

print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Lấy ra từ stack rỗng

pop() trên list rỗng gây lỗi IndexError.

Sai
item = stack.pop()
Cách sửa
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.

Sai
stack.insert(0, item)
stack.pop(0)
Cách sửa
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.

Tất cả thử thách