Login

Stack và Queue: hai cấu trúc dữ liệu quen thuộc như xếp đĩa và xếp hàng

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Cách đơn giản nhất để hiểu stack và queue là nhìn vào đời sống: chồng đĩa trong bếp và hàng người chờ mua trà sữa. Hai cấu trúc này khác nhau ở một điểm rất nhỏ nhưng quyết định cách chúng được dùng.

Stack: vào sau ra trước

Stack (ngăn xếp) hoạt động theo nguyên tắc LIFO - Last In, First Out. Bạn đặt đĩa mới lên đỉnh chồng và khi lấy, bạn cũng lấy đĩa trên cùng. Hai thao tác chính:

  • push: thêm phần tử vào đỉnh.
  • pop: lấy phần tử ở đỉnh ra.
  • peek: xem phần tử đỉnh mà không lấy.

Trong Python, bạn có thể dùng list như một stack:

stack = []
stack.append("A")   # push
stack.append("B")
stack.append("C")
print(stack.pop())  # C
print(stack.pop())  # B
print(stack)        # ['A']

Ứng dụng của stack

  • Nút Undo trong trình soạn thảo: thao tác gần nhất được hoàn tác trước.
  • Nút Back của trình duyệt: lịch sử trang xếp chồng.
  • Ngăn xếp lời gọi hàm: khi hàm A gọi hàm B, B chạy xong mới quay lại A.
  • Kiểm tra ngoặc cân bằng trong biểu thức.

Bài kiểm tra ngoặc là ví dụ kinh điển:

def ngoac_hop_le(s):
    cap = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in cap:
            if not stack or stack.pop() != cap[c]:
                return False
    return not stack

print(ngoac_hop_le("{[()]}"))   # True
print(ngoac_hop_le("([)]"))     # False

Queue: vào trước ra trước

Queue (hàng đợi) theo nguyên tắc FIFO - First In, First Out. Ai đến trước được phục vụ trước. Thao tác chính là enqueue (thêm vào cuối) và dequeue (lấy ra ở đầu).

Với Python, nên dùng collections.deque thay vì list, vì lấy phần tử đầu của list phải dời cả danh sách nên chậm:

from collections import deque

hang = deque()
hang.append("Lan")      # enqueue
hang.append("Minh")
hang.append("Hà")
print(hang.popleft())   # Lan  (dequeue)
print(hang.popleft())   # Minh
print(len(hang))        # 1

Ứng dụng của queue

  • Hàng chờ in: tài liệu gửi trước in trước.
  • Hàng đợi tác vụ trong hệ thống: gửi email, xử lý đơn hàng lần lượt.
  • Duyệt đồ thị theo chiều rộng (BFS) để tìm đường ngắn nhất.
  • Vòng lặp sự kiện xử lý click, phím bấm theo thứ tự xuất hiện.

So sánh nhanh

Tiêu chíStackQueue
Nguyên tắcLIFOFIFO
ThêmVào đỉnh (push)Vào cuối (enqueue)
LấyTừ đỉnh (pop)Từ đầu (dequeue)
Ví dụChồng đĩa, UndoXếp hàng, hàng chờ

Cả hai thao tác chính đều nhanh nếu cài đặt đúng, nên chúng được dùng rộng rãi khi cần xử lý dữ liệu theo thứ tự cố định.

Biến thể đáng biết

  • Deque: hàng đợi hai đầu, thêm lấy được cả hai phía.
  • Priority queue: phần tử có độ ưu tiên cao được ra trước, bất kể thứ tự vào; dùng trong lập lịch tác vụ và thuật toán đường đi.

Ví dụ: lịch sử trình duyệt với hai stack

Nút Back và Forward của trình duyệt có thể mô phỏng bằng hai stack:

class TrinhDuyet:
    def __init__(self, trang_chu):
        self.hien_tai = trang_chu
        self.lui = []
        self.tien = []

    def truy_cap(self, url):
        self.lui.append(self.hien_tai)
        self.hien_tai = url
        self.tien.clear()

    def back(self):
        if self.lui:
            self.tien.append(self.hien_tai)
            self.hien_tai = self.lui.pop()

    def forward(self):
        if self.tien:
            self.lui.append(self.hien_tai)
            self.hien_tai = self.tien.pop()

b = TrinhDuyet("trang-chu")
b.truy_cap("khoa-hoc")
b.truy_cap("bai-viet")
b.back()
print(b.hien_tai)   # khoa-hoc
b.forward()
print(b.hien_tai)   # bai-viet

Mỗi lần truy cập trang mới, danh sách "tiến" bị xóa, đúng như trình duyệt thật. Hãy thêm tính năng đếm số trang trong lịch sử như bài tập tiếp theo. Ví dụ này cho thấy hai cấu trúc đơn giản có thể mô tả một hành vi quen thuộc.

Lỗi thường gặp và bài tập

  1. Dùng list làm queue. ds.pop(0) phải dời toàn bộ phần tử phía sau nên chậm với dữ liệu lớn; hãy dùng deque.
  2. Pop từ stack rỗng gây IndexError. Luôn kiểm tra if stack: trước.
  3. Nhầm thứ tự: hỏi mình cái nào cần xử lý trước, cái mới nhất (stack) hay cái cũ nhất (queue).

Bài tập gợi ý: đảo ngược một chuỗi bằng stack; tính giá trị biểu thức hậu tố như 3 4 + 2 * (đẩy số vào stack, gặp phép toán thì lấy hai số ra tính rồi đẩy kết quả lại); mô phỏng hàng chờ ở quầy với mỗi khách mất một số phút phục vụ khác nhau. Bài biểu thức hậu tố đặc biệt hay vì nó cho thấy stack có thể thay thế cả việc phân tích ngoặc phức tạp.

Kết luận

Stack là chồng đĩa, queue là hàng người chờ, và khác biệt nằm ở đầu nào được lấy ra. Hãy thử tự cài đặt cả hai từ list, giải bài kiểm tra ngoặc và mô phỏng hàng chờ. Khi gặp bài toán cần thứ tự xử lý, bạn sẽ biết nên chọn cấu trúc nào.

Bạn có thể tiếp tục hành trình với những khóa học lập trình trên codebem.com, học theo tốc độ của riêng mình.

author_photo
Nguyễn Đình Cường

0 comment