Stack & QueueStacks & Queues

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Stack và queue là hai cấu trúc được định nghĩa không phải bởi cách chúng lưu dữ liệu mà bởi những gì chúng từ chối cho bạn làm. Cả hai đều chứa một dãy; cả hai đều cho bạn đúng một chỗ để thêm và một chỗ để lấy ra; không cái nào cho bạn thò tay vào giữa. Chính sự hạn chế đó là toàn bộ giá trị của chúng — bằng cách từ bỏ random access, bạn nhận được một cấu trúc mà mọi thao tác đều O(1), hành vi dễ dự đoán một cách hiển nhiên, và bản thân bảo đảm về thứ tự (LIFO hoặc FIFO) chính là thuật toán trong một số lượng bài toán đáng ngạc nhiên.

• Stack là Last-In-First-Out. Thứ bạn push cuối cùng là thứ pop ra đầu tiên. Chồng đĩa; lịch sử undo trong editor; call stack mà chương trình của bạn đang chạy trên đó ngay lúc này.
• Queue là First-In-First-Out. Thứ bạn enqueue đầu tiên là thứ dequeue ra đầu tiên. Hàng người xếp ở quầy; hàng đợi in ấn; ready queue trong scheduler của OS; hàng công việc tồn đọng phía sau một web server.

Chúng là abstract data type, không phải một layout cụ thể — interface là push/pop/peek và enqueue/dequeue/peek, và bạn có thể lót phía dưới bằng array hoặc linked list. Sự phân biệt giữa interface và implementation, được triển khai trong cấu trúc dữ liệu là gì, thể hiện rõ nhất ở đây: cùng một stack ADT được hiện thực bởi một list Python, bởi một linked list, bởi một array C cố định cộng một số nguyên, và bởi chính thanh ghi %rsp của CPU.

Note này dựng cả hai từ đầu theo cả hai cách biểu diễn, đi qua circular buffer — thứ làm cho queue dựa trên array thực sự là O(1) — và bao quát các mẫu hình mà chúng cung cấp sức mạnh: kiểm tra dấu ngoặc cân bằng, tính biểu thức, DFS so với BFS, monotonic stack, và deque.

Kiến thức nền tảng

Stack

   push(4)                 pop() -> 4
      |                        ^
      v                        |
   +-----+                  +-----+
   |  4  | <- top           |  3  | <- top
   +-----+                  +-----+
   |  3  |                  |  2  |
   +-----+                  +-----+
   |  2  |                  |  1  |
   +-----+                  +-----+
   |  1  | <- bottom        
   +-----+

   Mọi truy cập đều xảy ra ở một đầu. Đáy không thể chạm tới
   nếu không pop hết mọi thứ phía trên.

Các thao tác, tất cả đều O(1):

Thao tác	Ý nghĩa	Hành vi khi stack rỗng
push(x)	Đặt x lên đỉnh	—
pop()	Lấy ra và trả về đỉnh	Stack underflow — phải ném lỗi hoặc trả sentinel
peek() / top()	Trả về đỉnh mà không lấy ra	Underflow
is_empty()	Có gì trong đó không	—
size()	Đang có bao nhiêu phần tử	—

Một stack dung lượng cố định còn có thể overflow khi push. Đây không chỉ là chuyện sách vở: call stack phần cứng có kích thước cố định (thường 1–8 MB), và chạy vượt quá nó chính xác là StackOverflowError / RecursionError / segfault mà bạn nhận được từ đệ quy mất kiểm soát.

Stack dựa trên array

Cách hiện thực tự nhiên. Push và pop của stack đều xảy ra ở một đầu, và đầu rẻ của array là phía sau — nên đặt đỉnh stack ở cuối array và cả hai thao tác đều O(1) amortized mà không phải dịch chuyển gì cả.

class ArrayStack:
    """Stack lót bởi một dynamic array. CUỐI array là ĐỈNH stack —
    chính lựa chọn đó làm cho mọi thao tác là O(1)."""

    def __init__(self, iterable=()):
        self._data = []                            # list của Python CHÍNH LÀ dynamic array
        for item in iterable:
            self.push(item)

    def push(self, item):
        """O(1) amortized — chỉ O(n) ở lần resize hiếm hoi bên dưới."""
        self._data.append(item)

    def pop(self):
        """O(1) — không có gì dịch chuyển, ta chỉ giảm size."""
        if not self._data:
            raise IndexError("pop from empty stack")   # stack underflow
        return self._data.pop()

    def peek(self):
        """O(1) — nhìn mà không lấy ra."""
        if not self._data:
            raise IndexError("peek at empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

    def __repr__(self):
        return f"ArrayStack(bottom -> top: {self._data})"


s = ArrayStack([1, 2, 3])
s.push(4)
print(s)              # ArrayStack(bottom -> top: [1, 2, 3, 4])
print(s.pop())        # 4
print(s.peek())       # 3

Đừng dựng stack theo chiều ngược lại. Nếu bạn lấy index 0 làm đỉnh, push trở thành insert(0, x) và pop trở thành pop(0) — cả hai đều O(n), vì mọi phần tử phải dịch chuyển. Lựa chọn đầu nào làm đỉnh chính là toàn bộ khác biệt giữa O(1) và O(n). Đây là cách phổ biến nhất khiến người ta vô tình viết ra một stack bậc hai trong Python.

Stack dựa trên linked list

Push và pop ở head của một singly linked list đều O(1) mà không cần amortization và không có cú tăng vọt do resize:

class LinkedStack:
    """Stack lót bởi một singly linked list. Push/pop tại HEAD — cả hai O(1) worst case,
    không có cú tăng vọt do resize, đổi lại một pointer + một object header mỗi phần tử."""

    class _Node:
        __slots__ = ("value", "next")

        def __init__(self, value, next=None):
            self.value = value
            self.next = next

    def __init__(self, iterable=()):
        self._head = None                          # head là đỉnh của stack
        self._size = 0
        for item in iterable:
            self.push(item)

    def push(self, item):
        """O(1) worst case — không bao giờ phải copy."""
        self._head = self._Node(item, self._head)
        self._size += 1

    def pop(self):
        """O(1) worst case."""
        if self._head is None:
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        node.next = None                           # tách ra để tham chiếu cũ không đi tiếp được
        self._size -= 1
        return node.value

    def peek(self):
        if self._head is None:
            raise IndexError("peek at empty stack")
        return self._head.value

    def is_empty(self):
        return self._size == 0

    def __len__(self):
        return self._size


s = LinkedStack([1, 2, 3])
print(s.pop(), len(s))    # 3 2

	Dựa trên array	Dựa trên linked list
push	O(1) amortized, O(n) worst	O(1) worst case
pop / peek	O(1)	O(1)
Bộ nhớ mỗi phần tử	8 byte (pointer) + phần dư	~56 byte trong CPython
Hành vi cache	Xuất sắc (liên tục)	Kém (đuổi theo pointer)
Tăng vọt latency	Có — lần copy khi resize	Không
Kết luận	Lựa chọn mặc định	Chỉ khi cú tăng vọt do resize là không chấp nhận được (hard real-time)

Trong Python, cứ dùng list. append và pop vốn đã chính xác là các thao tác stack, chúng được viết bằng C, và nhanh hơn mọi thứ bạn có thể tự viết. Hãy dựng các class ở trên để hiểu chúng, còn production thì dùng list.

Queue

   enqueue ở PHÍA SAU, dequeue ở PHÍA TRƯỚC.

     dequeue <--- +-----+-----+-----+-----+ <--- enqueue
                  |  1  |  2  |  3  |  4  |
                  +-----+-----+-----+-----+
                  front                rear

   dequeue() -> 1, sau đó queue là [2, 3, 4] với front ở 2.

Thao tác	Ý nghĩa	Hành vi khi queue rỗng
enqueue(x)	Thêm x vào phía sau	—
dequeue()	Lấy ra và trả về phần tử phía trước	Queue underflow
peek() / front()	Trả về phần tử phía trước mà không lấy ra	Underflow
is_empty(), size()	—	—

Queue dựa trên array kiểu ngây thơ, và vì sao nó hỏng

Cách hiện thực hiển nhiên — list.append để enqueue, list.pop(0) để dequeue — là O(n) mỗi lần dequeue, vì xoá index 0 làm mọi phần tử còn lại dịch sang trái một ô:

   Trước pop(0):  [ 1 | 2 | 3 | 4 ]
   Sau đó:        [ 2 | 3 | 4 |   ]     <- 3 phần tử bị di chuyển thật sự

Xử lý n phần tử qua một queue như vậy tốn O(n²). Đây là cách vô tình tạo ra thuật toán bậc hai phổ biến thứ hai trong Python, sau việc nối chuỗi trong vòng lặp, và nó xuất hiện liên tục trong các BFS viết tay.

Cách sửa ngây thơ còn lại — giữ một index front và không bao giờ dịch chuyển, chỉ đẩy nó tiến lên — làm dequeue thành O(1) nhưng rò rỉ bộ nhớ: các ô phía trước front không bao giờ được tái sử dụng, nên một queue đã đi qua một triệu phần tử vẫn giữ một triệu ô chết dù hiện tại nó chỉ chứa ba phần tử.

Circular buffer (ring buffer)

Cách sửa thật sự là để queue vòng lại qua cuối một array cố định. Giữ một index front và một biến count; phía sau được tính bằng (front + count) % capacity. Giờ cả hai đầu đều O(1) và vùng chết ở phía trước được thu hồi tự động.

   capacity = 8, front = 5, count = 5   ->  ô rear = (5 + 5) % 8 = 2

   index:    0     1     2     3     4     5     6     7
          +-----+-----+-----+-----+-----+-----+-----+-----+
          |  D  |  E  |     |     |     |  A  |  B  |  C  |
          +-----+-----+-----+-----+-----+-----+-----+-----+
                         ^                 ^
                  enqueue kế tiếp      front (dequeue kế tiếp)

   Thứ tự logic: A B C D E     — buffer đã vòng qua cuối array.
   enqueue(F) ghi vào index 2. dequeue() trả về A và đặt front = 6.

class CircularQueue:
    """Queue FIFO trên circular buffer: enqueue và dequeue O(1), không dịch chuyển,
    không rò rỉ ô chết. Nhân đôi khi đầy."""

    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._front = 0                            # index của phần tử phía trước
        self._count = 0                            # đang có bao nhiêu phần tử sống

    def __len__(self):
        return self._count

    def is_empty(self):
        return self._count == 0

    def enqueue(self, item):
        """O(1) amortized. Phép modulo chính là thứ làm buffer vòng lại."""
        if self._count == len(self._data):
            self._resize(2 * len(self._data))
        rear = (self._front + self._count) % len(self._data)
        self._data[rear] = item
        self._count += 1

    def dequeue(self):
        """O(1) — chỉ đẩy index front tiến lên; không gì di chuyển."""
        if self._count == 0:
            raise IndexError("dequeue from empty queue")
        item = self._data[self._front]
        self._data[self._front] = None             # bỏ tham chiếu để GC giải phóng được
        self._front = (self._front + 1) % len(self._data)
        self._count -= 1
        return item

    def peek(self):
        if self._count == 0:
            raise IndexError("peek at empty queue")
        return self._data[self._front]

    def _resize(self, new_capacity):
        """O(n). Trải buffer đang vòng ra một buffer mới bắt đầu từ index 0 —
        đây là lý do vòng copy phải đi qua modulo chứ không phải một lệnh slice đơn giản."""
        old = self._data
        self._data = [None] * new_capacity
        walk = self._front
        for i in range(self._count):
            self._data[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

    def __iter__(self):
        for i in range(self._count):
            yield self._data[(self._front + i) % len(self._data)]

    def __repr__(self):
        return f"CircularQueue(front -> rear: {list(self)})"


q = CircularQueue(capacity=4)
for x in "ABCD":
    q.enqueue(x)
print(q.dequeue(), q.dequeue())    # A B
q.enqueue("E")
q.enqueue("F")                     # hai phần tử này vòng vào ô 0 và 1
print(q)                           # CircularQueue(front -> rear: ['C', 'D', 'E', 'F'])

Hai chi tiết đáng để ý. Thứ nhất, theo dõi count thay vì một index rear tránh được sự nhập nhằng đầy-hay-rỗng kinh điển: nếu chỉ có front và rear thì front == rear vừa nghĩa là rỗng vừa nghĩa là đầy, và cách chữa thông thường là hy sinh một ô. Thứ hai, self._data[self._front] = None khi dequeue rất quan trọng trong ngôn ngữ có garbage collection — không có nó, buffer giữ một tham chiếu sống tới object đã dequeue mãi mãi, và đó là một memory leak thật sự rất khó tìm.

Circular buffer dung lượng cố định (không resize — chỉ từ chối hoặc ghi đè khi đầy) có mặt khắp nơi trong system code: buffer I/O âm thanh và mạng, ring buffer của kernel (dmesg), queue lock-free một-producer-một-consumer, và cửa sổ lưu trữ của một metrics agent. Bộ nhớ bị chặn ở đó là tính năng, không phải hạn chế.

Queue dựa trên linked list

Head là phía trước, tail là phía sau. Cả hai O(1), không giới hạn dung lượng, không resize:

class LinkedQueue:
    """Queue FIFO trên singly linked list: dequeue ở head, enqueue ở tail.
    Tail pointer là thiết yếu — không có nó, enqueue là O(n)."""

    class _Node:
        __slots__ = ("value", "next")

        def __init__(self, value):
            self.value = value
            self.next = None

    def __init__(self):
        self._head = None                          # phía trước
        self._tail = None                          # phía sau
        self._size = 0

    def enqueue(self, item):
        """O(1) worst case — nhờ tail pointer."""
        node = self._Node(item)
        if self._tail is None:
            self._head = self._tail = node
        else:
            self._tail.next = node
            self._tail = node
        self._size += 1

    def dequeue(self):
        """O(1) worst case."""
        if self._head is None:
            raise IndexError("dequeue from empty queue")
        node = self._head
        self._head = node.next
        if self._head is None:                     # queue vừa trở thành rỗng
            self._tail = None
        self._size -= 1
        node.next = None
        return node.value

    def peek(self):
        if self._head is None:
            raise IndexError("peek at empty queue")
        return self._head.value

    def __len__(self):
        return self._size

Tổng hợp độ phức tạp

Thao tác	Array stack	Linked stack	Circular queue	Linked queue	collections.deque
Push / enqueue	O(1) amortized	O(1)	O(1) amortized	O(1)	O(1)
Pop / dequeue	O(1)	O(1)	O(1)	O(1)	O(1) (cả hai đầu)
Peek	O(1)	O(1)	O(1)	O(1)	O(1)
Truy cập index i	O(1) (nhưng không thuộc ADT)	O(n)	O(1) (nhưng không thuộc ADT)	O(n)	O(n) ở giữa
Tìm kiếm	O(n)	O(n)	O(n)	O(n)	O(n)
Bộ nhớ	O(n), dư ≤2×	O(n), overhead ~7×	O(n), dư ≤2×	O(n), overhead ~7×	O(n), theo block
Worst case một thao tác	O(n) (resize)	O(1)	O(n) (resize)	O(1)	O(1) amortized

Mọi lựa chọn ở đây đều là O(1) đối với các thao tác mà ADT thực sự phơi ra. Việc chọn giữa chúng hoàn toàn là chuyện hằng số, bộ nhớ và tăng vọt latency — không bao giờ là chuyện tiệm cận.

collections.deque — thứ bạn thực sự dùng

Deque (double-ended queue, đọc là “deck”) cho phép push và pop ở cả hai đầu. Nó tổng quát hoá cả hai cấu trúc: dùng một đầu thì được stack, dùng cả hai đầu thì được queue. collections.deque của Python là câu trả lời production cho “tôi cần một queue”:

from collections import deque

# Dùng như queue (FIFO)
q = deque()
q.append("a")            # enqueue vào phía sau     O(1)
q.append("b")
print(q.popleft())       # dequeue từ phía trước    O(1) — KHÔNG phải O(n) như list.pop(0)

# Dùng như stack (LIFO)
st = deque()
st.append(1)             # push   O(1)
print(st.pop())          # pop    O(1)

# Có giới hạn: cửa sổ trượt kích thước cố định, tự loại bỏ ở đầu kia
last_three = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    last_three.append(x)
print(last_three)        # deque([3, 4, 5], maxlen=3)

# Xoay là O(k), hữu ích cho round-robin scheduling
d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)                 # deque([4, 5, 1, 2, 3])

Cái giá của nó: CPython hiện thực deque như một doubly linked list của các block cố định (64 pointer mỗi block). Bạn được O(1) ở cả hai đầu mà không có lần copy khi resize, và locality tạm ổn trong phạm vi một block — nhưng index vào giữa là O(n), nên d[len(d)//2] phải đi qua từng block. Nếu bạn cần cả hai đầu nhanh lẫn index nhanh, bạn cần một cấu trúc khác.

Hai thứ nữa trong thư viện chuẩn đáng nhắc tên: queue.Queue là một blocking queue thread-safe với lock và ngữ nghĩa join() — dùng cho producer/consumer giữa các thread, không dùng cho thuật toán, vì việc khoá làm nó chậm hơn nhiều. heapq cho ta một priority queue, tức queue sắp theo độ ưu tiên thay vì theo thứ tự đến, được bàn trong heap và priority queue.

Khái niệm chính

Call stack

Stack quan trọng nhất trong ngành máy tính là cái mà chương trình của bạn đang chạy trên đó. Mỗi lời gọi hàm push một stack frame chứa địa chỉ trả về, các thanh ghi được lưu, tham số và biến cục bộ; mỗi lần return pop nó ra. Kỷ luật LIFO đúng chính xác cho việc này: một hàm được gọi sau phải trả về trước hàm đã gọi nó.

   def a(): b()
   def b(): c()
   def c(): return 1

   Trong lúc c() chạy:           Sau khi c() trả về:
   +----------------+            +----------------+
   | frame for c()  | <- sp      | frame for b()  | <- sp
   +----------------+            +----------------+
   | frame for b()  |            | frame for a()  |
   +----------------+            +----------------+
   | frame for a()  |            | frame for main |
   +----------------+            +----------------+
   | frame for main |
   +----------------+

Những hệ quả đáng ghi nhớ:

• Stack traceback chính là bản dump của stack này, in từ trên xuống. Đọc nó là đọc những lần push chưa được pop.
• Độ sâu đệ quy bị chặn bởi kích thước stack. Python chặn một cách nhân tạo (sys.setrecursionlimit, mặc định 1000) và ném RecursionError; C thì chỉ chạy vượt qua guard page và segfault. Xem đệ quy.
• Mọi thuật toán đệ quy đều có thể chuyển thành lặp bằng cách tự quản lý một stack tường minh. Đây không phải trò mua vui — nó là cách chạy DFS trên đồ thị một triệu node mà không làm nổ call stack, và là cách đưa “trạng thái” của một traversal đang tạm dừng vào một biến mà bạn có thể kiểm tra được.

def dfs_recursive(graph, start, visited=None):
    """Dùng CALL stack. Thanh lịch, nhưng bị giới hạn độ sâu."""
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited


def dfs_iterative(graph, start):
    """Cùng một traversal với stack TƯỜNG MINH. Không giới hạn độ sâu, và biên duyệt
    là một biến thật mà bạn có thể kiểm tra, log hoặc checkpoint."""
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()                         # LIFO -> depth-first
        if node in visited:
            continue
        visited.add(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                stack.append(neighbour)
    return visited

DFS so với BFS chỉ là đổi stack thành queue

Đây là minh chứng rõ ràng nhất rằng container chính là thuật toán. Hai traversal trong cấu trúc dữ liệu đồ thị khác nhau đúng một dòng:

from collections import deque


def traverse(graph, start, use_stack):
    """Đổi LIFO thành FIFO và depth-first trở thành breadth-first. Không gì khác thay đổi."""
    frontier = deque([start])
    visited = {start}
    order = []
    while frontier:
        node = frontier.pop() if use_stack else frontier.popleft()   # <-- khác biệt duy nhất
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                frontier.append(neighbour)
    return order


graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}
print(traverse(graph, "A", use_stack=True))    # DFS: ['A', 'C', 'F', 'B', 'E', 'D']
print(traverse(graph, "A", use_stack=False))   # BFS: ['A', 'B', 'C', 'D', 'E', 'F']

Thứ tự FIFO của BFS chính là thứ khiến nó tìm ra đường đi ngắn nhất trên đồ thị không trọng số — các node đi ra theo thứ tự khoảng cách không giảm dần tính từ nguồn, nên lần đầu tiên bạn tới được một node là qua một đường đi ngắn nhất. Stack không cho bảo đảm nào như vậy. Đó là lý do popleft() chứ không phải pop() mới quan trọng ở đây, và lý do dùng list.pop(0) thay cho deque.popleft() lặng lẽ biến một BFS O(V + E) thành O(V² + VE).

Dấu ngoặc cân bằng — bài toán stack kinh điển

Lý do stack giải được bài này: dấu ngoặc mở gần nhất là dấu phải được đóng tiếp theo, và đó chính xác là LIFO.

def is_balanced(text):
    """O(n) thời gian, O(n) bộ nhớ (worst case '((((((' push tất cả)."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)                       # nhớ lại thứ sẽ phải đóng sau này
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False                       # sai dấu đóng, hoặc chẳng có gì đang mở
    return not stack                               # còn sót gì đang mở nghĩa là không cân bằng


print(is_balanced("{[()()]}"))   # True
print(is_balanced("{[(])}"))     # False — ']' đóng cho một '(' 
print(is_balanced("(("))         # False — stack chưa rỗng khi kết thúc

Cùng hình dạng đó giải được cả một họ bài toán: khớp tag HTML/XML, kiểm tra lồng nhau trong một config parser, kiểm tra mỗi BEGIN đều có END. Bất cứ khi nào tính đúng đắn phụ thuộc vào “thứ chưa khớp gần nhất”, đó là một stack.

Tính biểu thức

Stack là cách máy tính bỏ túi và compiler tính biểu thức số học. Ký pháp Reverse Polish (hậu tố) không cần dấu ngoặc và được tính bằng một stack giá trị duy nhất:

def eval_rpn(tokens):
    """Tính biểu thức reverse Polish. O(n) thời gian, O(n) bộ nhớ.
    '3 4 + 2 *' nghĩa là (3 + 4) * 2 = 14."""
    stack = []
    for token in tokens:
        if token in {"+", "-", "*", "/"}:
            b = stack.pop()                        # thứ tự quan trọng: b được push sau
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))           # cắt về phía 0
        else:
            stack.append(int(token))
    return stack.pop()


print(eval_rpn("3 4 + 2 *".split()))         # 14
print(eval_rpn("5 1 2 + 4 * + 3 -".split())) # 14

Chuyển từ trung tố (3 + 4 * 2) sang hậu tố dùng thêm một stack thứ hai cho toán tử — thuật toán shunting-yard của Dijkstra — trong đó một toán tử nằm lại trên stack cho tới khi gặp một toán tử có độ ưu tiên thấp hơn hoặc bằng. Các máy ảo dựa trên stack (JVM, chính bytecode interpreter của CPython, WebAssembly) thực thi ở dạng hậu tố đúng vì lý do này: nó không cần cấp phát thanh ghi và operand stack lo hết phần ghi sổ.

Monotonic stack

Monotonic stack giữ cho nội dung của nó luôn có thứ tự (tăng hoặc giảm) bằng cách pop bỏ mọi thứ làm phá vỡ thứ tự đó. Nó trả lời các truy vấn “phần tử lớn hơn kế tiếp / nhỏ hơn trước đó” cho cả một array trong tổng cộng O(n), và đây là mẹo chuẩn cho một họ bài toán trông có vẻ O(n²).

def next_greater_element(nums):
    """Với mỗi phần tử, tìm phần tử kế tiếp bên phải lớn hơn nó (-1 nếu không có).
    O(n) thời gian dù trông có vẻ bậc hai: mỗi index được push đúng một lần và pop
    tối đa một lần, nên vòng while bên trong chạy TỔNG CỘNG O(n) lần qua cả vòng ngoài."""
    result = [-1] * len(nums)
    stack = []                                     # chứa INDEX, giá trị giảm dần
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = value            # `value` là đáp án cho index đó
        stack.append(i)
    return result                                  # thứ còn sót trên stack giữ nguyên -1


print(next_greater_element([2, 1, 2, 4, 3]))       # [4, 2, 4, -1, -1]


def largest_rectangle_in_histogram(heights):
    """Hình chữ nhật lớn nhất dưới một histogram. O(n) với monotonic stack tăng dần —
    cách vét cạn là O(n^2). Khi một cột bị pop, ta mới biết được hình chữ nhật của nó
    có thể kéo dài về bên trái tới đâu: tới ngay sau đỉnh stack mới."""
    stack = []                                     # index, chiều cao tăng dần
    best = 0
    for i, h in enumerate(heights + [0]):          # sentinel 0 để xả sạch stack ở cuối
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0   # cột vừa pop kéo dài về tới đây
            best = max(best, height * (i - left))
        stack.append(i)
    return best


print(largest_rectangle_in_histogram([2, 1, 5, 6, 2, 3]))   # 10

Lập luận amortized mới là phần quan trọng: vòng while trông như làm thuật toán thành bậc hai, nhưng mỗi index vào stack đúng một lần và ra tối đa một lần, nên tổng công qua tất cả các vòng là O(n). Đây chính là kiểu phân tích tổng gộp giống như phép nhân đôi của dynamic array trong array.

Người anh em hình dạng queue là monotonic deque, tính giá trị lớn nhất trên cửa sổ trượt trong O(n) — xem hai con trỏ và cửa sổ trượt.

Hai stack tạo thành một queue

Một kết quả thú vị với bài học thật về amortized analysis. Giữ một stack in và một stack out; enqueue push vào in, dequeue pop từ out, và nạp lại out bằng cách dốc ngược in khi out rỗng. Việc đảo ngược hai lần biến LIFO thành FIFO.

class QueueFromStacks:
    """FIFO từ hai stack LIFO. Amortized O(1) mỗi thao tác dù có bước chuyển O(n):
    mỗi phần tử được chuyển từ `in` sang `out` đúng một lần trong đời nó."""

    def __init__(self):
        self._in = []
        self._out = []

    def enqueue(self, item):
        self._in.append(item)                      # luôn luôn O(1)

    def dequeue(self):
        if not self._out:                          # chỉ nạp lại khi `out` đã cạn
            while self._in:
                self._out.append(self._in.pop())   # O(n), nhưng amortized O(1) mỗi phần tử
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()


q = QueueFromStacks()
for x in [1, 2, 3]:
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # 1 2 — thứ tự FIFO được giữ nguyên

Đây là một câu hỏi phỏng vấn được ưa chuộng, và đáp án được mong đợi không phải là đoạn code (vốn rất ngắn) mà là lập luận amortized: một phần tử được push vào in một lần, chuyển sang out một lần, và pop ra một lần — ba thao tác O(1) trong suốt vòng đời, nên n thao tác tốn tổng cộng O(n).

Chúng xuất hiện ở đâu trong hệ thống thật

• Undo/redo — hai stack: undo pop từ cái này và push sang cái kia.
• Nút back/forward của trình duyệt — cũng chính mẫu hai stack đó.
• Backtracking — trạng thái tìm kiếm là một stack; “hoàn tác lựa chọn cuối” là một lần pop. Xem backtracking.
• Task scheduling và work queue — các queue FIFO đứng trước thread pool, message broker và job runner. Backpressure là thứ xảy ra khi queue có giới hạn và bị đầy.
• Đệm request trong web server — accept queue là một FIFO có giới hạn; tràn nghĩa là rớt kết nối.
• Pipeline producer/consumer — một queue có giới hạn tách rời tốc độ producer khỏi tốc độ consumer và chặn được lượng bộ nhớ. Xem caching và big data và tính toán phân tán.
• Ring buffer của kernel và driver — circular queue dung lượng cố định cho log message, gói tin mạng, mẫu âm thanh.
• BFS và duyệt cây theo tầng — xem cấu trúc dữ liệu cây và thuật toán đường đi ngắn nhất.

Best Practices

• Dùng collections.deque cho mọi queue trong Python, không bao giờ dùng list. list.pop(0) là O(n) và biến một BFS O(V + E) thành bậc hai. Đây là điều giá trị nhất trên trang này.
• list là một stack hoàn toàn ổn. append và pop vốn đã O(1) ở đúng đầu. Đừng bọc nó vào một class trừ khi bạn cần kỷ luật về kiểu.
• Đặt đỉnh stack ở cuối array. Lấy index 0 làm đỉnh biến mọi thao tác thành O(n).
• Quyết định rõ ràng pop-trên-rỗng làm gì. Ném lỗi (IndexError của Python), trả về None, hay trả về cặp (ok, value) đều hợp lý — nhưng lặng lẽ trả None rồi để nó lan đi thì không, vì bug sẽ lộ ra ở rất xa nguyên nhân.
• Giới hạn queue trong production. Một work queue không giới hạn không báo lỗi; nó lớn dần cho tới khi tiến trình bị OOM-kill, thường là vào lúc tệ nhất. Queue có giới hạn tạo ra backpressure, và đó là một dạng lỗi bạn nhìn thấy và xử lý được.
• Gán None cho ô đã dequeue trong circular buffer ở các ngôn ngữ có garbage collection, nếu không bạn giữ sống các object đã chết.
• Theo dõi count, không chỉ front và rear, trong ring buffer — nếu không thì đầy và rỗng không phân biệt được và bạn phải hy sinh một ô để phân biệt.
• Chuyển đệ quy sâu thành stack tường minh. Nếu độ sâu đầu vào phụ thuộc dữ liệu (một cây do người dùng cung cấp, một đồ thị hình dạng bất kỳ), stack tường minh là khác biệt giữa chạy được và RecursionError trên production.
• Nghĩ tới monotonic stack khi bài toán hỏi “phần tử lớn hơn kế tiếp”, “nhỏ hơn trước đó”, hoặc hình chữ nhật/đoạn lớn nhất. Cách vét cạn O(n²) thường chính là cái bẫy được cài sẵn.
• Đừng dùng queue.Queue cho thuật toán đơn luồng. Nó thread-safe nên có lock và chậm; deque mới là thứ bạn cần trừ khi thực sự có nhiều thread tham gia.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Stack (abstract data type) — Wikipedia
• Queue (abstract data type) — Wikipedia
• Circular buffer — Wikipedia
• Double-ended queue — Wikipedia
• Call stack — Wikipedia
• Shunting yard algorithm — Wikipedia
• Reverse Polish notation — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 10: Elementary Data Structures
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — collections.deque
• Python Documentation — queue module
• Python Documentation — Using lists as stacks and queues
• VisuAlgo — Linked list, stack and queue visualisation
• Big-O Cheat Sheet

   push(4)                 pop() -> 4
      |                        ^
      v                        |
   +-----+                  +-----+
   |  4  | <- top           |  3  | <- top
   +-----+                  +-----+
   |  3  |                  |  2  |
   +-----+                  +-----+
   |  2  |                  |  1  |
   +-----+                  +-----+
   |  1  | <- bottom        
   +-----+

   All access happens at one end. The bottom is unreachable
   without popping everything above it.

class ArrayStack:
    """Stack backed by a dynamic array. The array's END is the stack's TOP —
    that choice is what makes every operation O(1)."""

    def __init__(self, iterable=()):
        self._data = []                            # a Python list IS a dynamic array
        for item in iterable:
            self.push(item)

    def push(self, item):
        """O(1) amortized — O(n) only on the rare underlying resize."""
        self._data.append(item)

    def pop(self):
        """O(1) — nothing shifts, we only decrement the size."""
        if not self._data:
            raise IndexError("pop from empty stack")   # stack underflow
        return self._data.pop()

    def peek(self):
        """O(1) — look without removing."""
        if not self._data:
            raise IndexError("peek at empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

    def __repr__(self):
        return f"ArrayStack(bottom -> top: {self._data})"


s = ArrayStack([1, 2, 3])
s.push(4)
print(s)              # ArrayStack(bottom -> top: [1, 2, 3, 4])
print(s.pop())        # 4
print(s.peek())       # 3

class LinkedStack:
    """Stack backed by a singly linked list. Push/pop at the HEAD — both O(1) worst case,
    with no resize spike, at the cost of one pointer + one object header per element."""

    class _Node:
        __slots__ = ("value", "next")

        def __init__(self, value, next=None):
            self.value = value
            self.next = next

    def __init__(self, iterable=()):
        self._head = None                          # the head is the top of the stack
        self._size = 0
        for item in iterable:
            self.push(item)

    def push(self, item):
        """O(1) worst case — no copying, ever."""
        self._head = self._Node(item, self._head)
        self._size += 1

    def pop(self):
        """O(1) worst case."""
        if self._head is None:
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        node.next = None                           # detach so a stale ref cannot walk on
        self._size -= 1
        return node.value

    def peek(self):
        if self._head is None:
            raise IndexError("peek at empty stack")
        return self._head.value

    def is_empty(self):
        return self._size == 0

    def __len__(self):
        return self._size


s = LinkedStack([1, 2, 3])
print(s.pop(), len(s))    # 3 2

   enqueue at the REAR, dequeue from the FRONT.

     dequeue <--- +-----+-----+-----+-----+ <--- enqueue
                  |  1  |  2  |  3  |  4  |
                  +-----+-----+-----+-----+
                  front                rear

   dequeue() -> 1, then the queue is [2, 3, 4] with front at 2.

   Before pop(0):  [ 1 | 2 | 3 | 4 ]
   After:          [ 2 | 3 | 4 |   ]     <- 3 elements physically moved

   capacity = 8, front = 5, count = 5   ->  rear slot = (5 + 5) % 8 = 2

   index:    0     1     2     3     4     5     6     7
          +-----+-----+-----+-----+-----+-----+-----+-----+
          |  D  |  E  |     |     |     |  A  |  B  |  C  |
          +-----+-----+-----+-----+-----+-----+-----+-----+
                         ^                 ^
                    next enqueue        front (next dequeue)

   Logical order: A B C D E     — the buffer wrapped past the end of the array.
   enqueue(F) writes index 2. dequeue() returns A and sets front = 6.

class CircularQueue:
    """FIFO queue on a circular buffer: O(1) enqueue and dequeue, no shifting,
    no leaked slots. Grows by doubling when full."""

    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._front = 0                            # index of the front element
        self._count = 0                            # how many elements are live

    def __len__(self):
        return self._count

    def is_empty(self):
        return self._count == 0

    def enqueue(self, item):
        """O(1) amortized. The modulo is what makes the buffer wrap."""
        if self._count == len(self._data):
            self._resize(2 * len(self._data))
        rear = (self._front + self._count) % len(self._data)
        self._data[rear] = item
        self._count += 1

    def dequeue(self):
        """O(1) — advance the front index; nothing moves."""
        if self._count == 0:
            raise IndexError("dequeue from empty queue")
        item = self._data[self._front]
        self._data[self._front] = None             # drop the reference so the GC can free it
        self._front = (self._front + 1) % len(self._data)
        self._count -= 1
        return item

    def peek(self):
        if self._count == 0:
            raise IndexError("peek at empty queue")
        return self._data[self._front]

    def _resize(self, new_capacity):
        """O(n). Unroll the wrapped buffer into a fresh one starting at index 0 —
        this is why the copy must go through the modulo, not a plain slice."""
        old = self._data
        self._data = [None] * new_capacity
        walk = self._front
        for i in range(self._count):
            self._data[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

    def __iter__(self):
        for i in range(self._count):
            yield self._data[(self._front + i) % len(self._data)]

    def __repr__(self):
        return f"CircularQueue(front -> rear: {list(self)})"


q = CircularQueue(capacity=4)
for x in "ABCD":
    q.enqueue(x)
print(q.dequeue(), q.dequeue())    # A B
q.enqueue("E")
q.enqueue("F")                     # these wrap into slots 0 and 1
print(q)                           # CircularQueue(front -> rear: ['C', 'D', 'E', 'F'])

class LinkedQueue:
    """FIFO queue on a singly linked list: dequeue at the head, enqueue at the tail.
    The tail pointer is essential — without it, enqueue is O(n)."""

    class _Node:
        __slots__ = ("value", "next")

        def __init__(self, value):
            self.value = value
            self.next = None

    def __init__(self):
        self._head = None                          # front
        self._tail = None                          # rear
        self._size = 0

    def enqueue(self, item):
        """O(1) worst case — thanks to the tail pointer."""
        node = self._Node(item)
        if self._tail is None:
            self._head = self._tail = node
        else:
            self._tail.next = node
            self._tail = node
        self._size += 1

    def dequeue(self):
        """O(1) worst case."""
        if self._head is None:
            raise IndexError("dequeue from empty queue")
        node = self._head
        self._head = node.next
        if self._head is None:                     # queue is now empty
            self._tail = None
        self._size -= 1
        node.next = None
        return node.value

    def peek(self):
        if self._head is None:
            raise IndexError("peek at empty queue")
        return self._head.value

    def __len__(self):
        return self._size

from collections import deque

# As a queue (FIFO)
q = deque()
q.append("a")            # enqueue at the rear      O(1)
q.append("b")
print(q.popleft())       # dequeue from the front   O(1) — NOT O(n) like list.pop(0)

# As a stack (LIFO)
st = deque()
st.append(1)             # push   O(1)
print(st.pop())          # pop    O(1)

# Bounded: a fixed-size sliding window that discards from the other end automatically
last_three = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    last_three.append(x)
print(last_three)        # deque([3, 4, 5], maxlen=3)

# Rotation is O(k), useful for round-robin scheduling
d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)                 # deque([4, 5, 1, 2, 3])

   def a(): b()
   def b(): c()
   def c(): return 1

   During c():                   After c() returns:
   +----------------+            +----------------+
   | frame for c()  | <- sp      | frame for b()  | <- sp
   +----------------+            +----------------+
   | frame for b()  |            | frame for a()  |
   +----------------+            +----------------+
   | frame for a()  |            | frame for main |
   +----------------+            +----------------+
   | frame for main |
   +----------------+

def dfs_recursive(graph, start, visited=None):
    """Uses the CALL stack. Elegant, but depth-limited."""
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited


def dfs_iterative(graph, start):
    """Same traversal with an EXPLICIT stack. No depth limit, and the frontier
    is a real variable you can inspect, log, or checkpoint."""
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()                         # LIFO -> depth-first
        if node in visited:
            continue
        visited.add(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                stack.append(neighbour)
    return visited

from collections import deque


def traverse(graph, start, use_stack):
    """Change LIFO to FIFO and depth-first becomes breadth-first. Nothing else changes."""
    frontier = deque([start])
    visited = {start}
    order = []
    while frontier:
        node = frontier.pop() if use_stack else frontier.popleft()   # <-- the only difference
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                frontier.append(neighbour)
    return order


graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}
print(traverse(graph, "A", use_stack=True))    # DFS: ['A', 'C', 'F', 'B', 'E', 'D']
print(traverse(graph, "A", use_stack=False))   # BFS: ['A', 'B', 'C', 'D', 'E', 'F']

def is_balanced(text):
    """O(n) time, O(n) space (worst case '((((((' pushes everything)."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)                       # remember what must close later
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False                       # wrong closer, or nothing was open
    return not stack                               # anything left open means unbalanced


print(is_balanced("{[()()]}"))   # True
print(is_balanced("{[(])}"))     # False — ']' closes a '(' 
print(is_balanced("(("))         # False — stack not empty at the end

def eval_rpn(tokens):
    """Evaluate reverse Polish notation. O(n) time, O(n) space.
    '3 4 + 2 *' means (3 + 4) * 2 = 14."""
    stack = []
    for token in tokens:
        if token in {"+", "-", "*", "/"}:
            b = stack.pop()                        # order matters: b was pushed second
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))           # truncate toward zero
        else:
            stack.append(int(token))
    return stack.pop()


print(eval_rpn("3 4 + 2 *".split()))         # 14
print(eval_rpn("5 1 2 + 4 * + 3 -".split())) # 14

def next_greater_element(nums):
    """For each element, the next element to its right that is larger (-1 if none).
    O(n) time even though it looks quadratic: each index is pushed once and popped
    at most once, so the inner while loop runs O(n) times TOTAL across the outer loop."""
    result = [-1] * len(nums)
    stack = []                                     # holds INDICES, values decreasing
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = value            # `value` is the answer for that index
        stack.append(i)
    return result                                  # anything left on the stack keeps -1


print(next_greater_element([2, 1, 2, 4, 3]))       # [4, 2, 4, -1, -1]


def largest_rectangle_in_histogram(heights):
    """Largest rectangle under a histogram. O(n) with a monotonic increasing stack —
    the brute force is O(n^2). When a bar is popped, we finally know how far left
    its rectangle could have extended: to just after the new stack top."""
    stack = []                                     # indices, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):          # sentinel 0 flushes the stack at the end
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0   # the popped bar extends back to here
            best = max(best, height * (i - left))
        stack.append(i)
    return best


print(largest_rectangle_in_histogram([2, 1, 5, 6, 2, 3]))   # 10

class QueueFromStacks:
    """FIFO from two LIFO stacks. Amortized O(1) per operation despite the O(n) transfer:
    each element is moved from `in` to `out` exactly once in its lifetime."""

    def __init__(self):
        self._in = []
        self._out = []

    def enqueue(self, item):
        self._in.append(item)                      # O(1) always

    def dequeue(self):
        if not self._out:                          # only refill when `out` is exhausted
            while self._in:
                self._out.append(self._in.pop())   # O(n), but amortized O(1) per element
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()


q = QueueFromStacks()
for x in [1, 2, 3]:
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # 1 2 — FIFO order preserved