Wiki › Cấu trúc dữ liệu › Ngăn xếp & Hàng đợi

Ngăn xếp & Hàng đợi

huunguyen Updated Tháng sáu 2, 2026

Ngăn xếp (stack) và hàng đợi (queue) là hai cấu trúc dữ liệu tuyến tính cơ bản nhất: chúng chỉ cho phép thêm/lấy phần tử ở đầu mút chứ không truy cập giữa chừng. Đổi lại sự hạn chế đó, mọi thao tác thêm/lấy đều chạy trong $O (1)$ . Chính nhờ trật tự thêm/lấy được quy định chặt chẽ mà chúng giải gọn nhiều bài toán: kiểm tra dãy ngoặc, mô phỏng "lấy ra phần tử gần nhất", duyệt BFS, tìm phần tử lớn hơn kế tiếp (monotonic stack), hay trượt cửa sổ cực trị (monotonic deque).

Ý tưởng / Trực giác

Cả hai cấu trúc đều là "đường ống" một chiều, khác nhau ở chỗ phần tử nào ra trước.

Ngăn xếp — LIFO (Last In, First Out): phần tử vào sau cùng thì ra trước tiên, giống chồng đĩa: đĩa đặt lên trên cùng là đĩa được lấy ra đầu tiên. Vì sao điều này hữu ích? Khi bài toán có cấu trúc lồng nhau (ngoặc trong ngoặc, lời gọi hàm trong lời gọi hàm, dấu ngoặc mở đang chờ một dấu đóng tương ứng), thì cái mở gần nhất luôn là cái cần được đóng trước nhất — đúng đặc tính LIFO. Stack cho phép luôn truy cập "phần tử mới nhất chưa xử lý" trong $O (1)$ .
Hàng đợi — FIFO (First In, First Out): phần tử vào trước thì ra trước, đúng như xếp hàng mua vé: ai đến trước được phục vụ trước. FIFO phù hợp khi cần xử lý theo đúng thứ tự đến, ví dụ BFS phải thăm các đỉnh theo từng lớp khoảng cách tăng dần, nên đỉnh nào được phát hiện trước (gần nguồn hơn) phải được mở rộng trước.
Hàng đợi hai đầu — deque (double-ended queue): tổng quát hơn, cho phép thêm/xoá ở cả hai đầu trong $O (1)$ . Nhờ đó nó vừa làm được stack, vừa làm được queue, và đặc biệt dùng cho monotonic deque trong bài cực trị cửa sổ trượt.

Điểm mấu chốt cần nhớ: ta đánh đổi khả năng truy cập tự do (như mảng/vector) để lấy sự đơn giản và đảm bảo $O (1)$ cho thao tác ở đầu mút. Khi bài toán chỉ cần "lấy phần tử gần nhất" hoặc "lấy phần tử cũ nhất", đó chính là tín hiệu dùng stack hoặc queue.

Ví dụ chạy tay

Stack — kiểm tra dãy ngoặc `(())()`

Duyệt từng ký tự: gặp ( thì đẩy vào stack, gặp ) thì lấy một ( ra để ghép cặp. Nếu lúc cần lấy mà stack rỗng thì sai; duyệt xong mà stack chưa rỗng cũng sai.

Chuỗi:  ( ( ) ) ( )
Bước:   1 2 3 4 5 6

b1 '(' push   -> stack: [ ( ]
b2 '(' push   -> stack: [ (  ( ]      <- đỉnh là '(' vừa vào
b3 ')' pop    -> stack: [ ( ]          ghép với '(' gần nhất
b4 ')' pop    -> stack: [ ]            ghép nốt cặp ngoài cùng
b5 '(' push   -> stack: [ ( ]
b6 ')' pop    -> stack: [ ]

Kết thúc: stack rỗng  => HỢP LỆ (YES)

So sánh nhanh với chuỗi sai )(: bước 1 gặp ) mà stack rỗng -> không có ( nào để ghép -> KHÔNG hợp lệ.

Queue — xử lý theo thứ tự đến

Đẩy 1, 2, 3 vào queue rồi lấy lần lượt. Phần tử ra luôn là phần tử vào sớm nhất:

push 1        front -> [ 1 ] <- back
push 2        front -> [ 1 2 ] <- back
push 3        front -> [ 1 2 3 ] <- back
            ^front          ^back

pop -> lấy 1  [ 2 3 ]
pop -> lấy 2  [ 3 ]
pop -> lấy 3  [ ]
Thứ tự lấy ra: 1, 2, 3  (đúng thứ tự vào)

Cài đặt

Ngăn xếp (`std::stack`)

#include <stack>
stack<int> st;
st.push(1); st.push(2); st.push(3); // đáy 1, đỉnh 3
cout << st.top();   // 3 (phần tử vào sau cùng)
st.pop();           // bỏ 3; LƯU Ý: pop() KHÔNG trả về giá trị
cout << st.size();  // 2
// LUÔN kiểm tra rỗng trước khi top()/pop()
if (!st.empty()) st.pop();

Kiểm tra dãy ngoặc bằng stack (chỉ cần đếm vì 1 loại ngoặc, nhưng dùng stack để tổng quát cho nhiều loại):

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);          // ngoặc mở: chờ ghép
        else {                              // ngoặc đóng
            if (st.empty()) return false;   // không có '(' để ghép -> sai
            st.pop();                       // ghép với '(' gần nhất
        }
    }
    return st.empty();                      // còn '(' thừa -> sai
}

Ứng dụng kinh điển: Monotonic Stack (tìm phần tử lớn hơn kế tiếp)

// res[i] = giá trị phần tử lớn hơn a[i] đầu tiên nằm bên phải, -1 nếu không có
vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st; // lưu CHỈ SỐ, các giá trị tương ứng giảm dần từ đáy lên đỉnh
    for (int i = 0; i < n; i++) {
        // a[i] lớn hơn các phần tử đang chờ ở đỉnh -> chính nó là đáp án của chúng
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

Hàng đợi (`std::queue`)

#include <queue>
queue<int> q;
q.push(1); q.push(2); q.push(3);
cout << q.front();  // 1 (phần tử vào sớm nhất)
cout << q.back();   // 3 (phần tử vào muộn nhất)
q.pop();            // bỏ phần tử đầu (1)

Ứng dụng kinh điển: BFS (duyệt theo lớp)

// dist[v] = số cạnh ít nhất từ start tới v
vector<int> bfs(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();      // lấy đỉnh phát hiện sớm nhất
        for (int v : adj[u])
            if (dist[v] == -1) {         // chưa thăm
                dist[v] = dist[u] + 1;
                q.push(v);
            }
    }
    return dist;
}

Deque (`std::deque`)

#include <deque>
deque<int> dq;
dq.push_back(2);   // [2]
dq.push_front(1);  // [1, 2]
dq.push_back(3);   // [1, 2, 3]
cout << dq.front() << ' ' << dq.back(); // 1 3
dq.pop_front();    // [2, 3]
dq.pop_back();     // [2]

Python tương đương:

# stack: dùng list
st = []
st.append(1); st.append(2)
st[-1]      # đỉnh
st.pop()

# queue / deque: dùng collections.deque (O(1) hai đầu)
from collections import deque
q = deque()
q.append(1); q.append(2)   # vào cuối
q[0]                       # đầu hàng
q.popleft()                # lấy đầu (FIFO)

Độ phức tạp

Thao tác	Stack	Queue	Deque
push / thêm	$O (1)$	$O (1)$	$O (1)$ hai đầu
pop / lấy	$O (1)$	$O (1)$	$O (1)$ hai đầu
xem đầu/đỉnh	$O (1)$	$O (1)$	$O (1)$ hai đầu

Vì sao $O (1)$ : stack và queue thực chất chỉ ghi/đọc ở một (hoặc hai) đầu của vùng nhớ liên tục hoặc danh sách liên kết, không phải dịch chuyển các phần tử còn lại. std::stack và std::queue mặc định bọc quanh std::deque, nên các thao tác đầu mút là hằng số (phân bổ lại bộ nhớ theo khối, nên biên độ trung bình amortized vẫn $O (1)$ ).

Bộ nhớ: $O (N)$ với $N$ là số phần tử đang chứa. Hai thuật toán điển hình:

Monotonic stack: mỗi phần tử được push đúng một lần và pop tối đa một lần, nên dù có vòng while lồng bên trong, tổng số thao tác trên toàn bộ vòng lặp vẫn là $O (N)$ — đây là lập luận amortized quan trọng nhất cần nắm.
BFS: mỗi đỉnh vào queue đúng một lần, mỗi cạnh xét đúng một lần, nên $O (V + E)$ thời gian và $O (V)$ bộ nhớ.

⚠️ Lỗi thường gặp

Gọi top()/front()/pop() khi rỗng (undefined behavior): đây là lỗi crash/sai kết quả phổ biến nhất. Luôn kiểm tra if (!st.empty()) trước. Trong bài kiểm tra ngoặc, quên kiểm tra rỗng khi gặp ) sẽ cho kết quả sai với chuỗi như )(.
Tưởng pop() trả về giá trị: trong C++, st.pop() chỉ xoá phần tử và không trả về gì. Phải đọc bằng top()/front() trước, rồi mới pop(). Viết int x = st.pop(); không biên dịch được.
Nhầm LIFO với FIFO: dùng stack cho bài cần xử lý theo thứ tự đến (hoặc ngược lại) sẽ ra đáp án sai dù code chạy trơn tru. Hỏi rõ: "phần tử nào cần ra trước?" — gần nhất thì stack, cũ nhất thì queue.
Tin rằng monotonic stack là $O (N^{2})$ vì có vòng while lồng: thực ra mỗi phần tử chỉ bị pop một lần trên toàn bộ quá trình, nên tổng vẫn $O (N)$ . Ngược lại, đừng vô tình biến nó thành $O (N^{2})$ bằng cách quét lại từ đầu mảng trong mỗi bước.
Dùng std::queue/std::stack rồi cố truy cập phần tử giữa: hai cấu trúc này không cho phép duyệt hay lập chỉ mục. Nếu cần điều đó, hãy dùng deque hoặc vector trực tiếp.
Tràn số khi cộng giá trị phần tử: nếu bài cộng dồn các giá trị lấy ra (tổng tiền, tổng phần tử...) với $N$ lớn và $a_{i}$ tới $10^{9}$ , hãy dùng long long cho biến tổng, tránh tràn int.
Hiệu năng I/O: với $N$ lớn (vd $2 \times 10^{5}$ ), thêm ios_base::sync_with_stdio(false); cin.tie(nullptr); để tránh TLE do nhập/xuất chậm.

Biến thể / Mở rộng

Monotonic deque cho cực trị cửa sổ trượt (sliding window maximum/minimum) trong $O (N)$ : giữ deque các chỉ số mà giá trị đơn điệu, loại đầu khi rời cửa sổ.
Hàng đợi ưu tiên (priority queue / heap): khi cần lấy ra phần tử lớn/nhỏ nhất thay vì cũ nhất — xem trang Heap.
Stack mô phỏng đệ quy: chuyển DFS đệ quy thành vòng lặp dùng stack tường minh để tránh tràn ngăn xếp lời gọi.
Hàng đợi bằng hai stack / deque bằng amortized: kỹ thuật cài đặt một cấu trúc bằng cấu trúc kia, hữu ích khi cần thêm thao tác như lấy min/max trong $O (1)$ amortized.

Bài tập luyện

Kiểm Tra Ngoặc (spellcheck) — (Học việc) Bài nhập môn stack kinh điển: ghép cặp ngoặc, nhận diện tín hiệu LIFO.
Hàng đợi tại trạm xe buýt (queuebus) — (Nghiệp dư) Mô phỏng FIFO: phục vụ các nhóm theo đúng thứ tự xếp hàng.
Nồi Thuốc Phép (cauldron) — (Trung cấp) Đẩy/lấy nguyên liệu "gần nhất" — đúng bản chất push/pop của stack, in ra từ đáy lên.
Rửa bát (dishes) — (Nâng cao) Mô phỏng stack LIFO kết hợp tham lam: tìm tiền tố dài nhất xử lý được.