STACK
Ngăn xếp trong C++

Stack là gì?

Stack là cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO: Last In, First Out, nghĩa là phần tử được đưa vào sau cùng sẽ được lấy ra trước tiên.

Phần tử ở trên cùng của stack gọi là đỉnh stack, truy cập bằng hàm top().

Ví dụ thực tế

Hãy tưởng tượng một chồng sách đặt trên bàn. Cuốn sách đặt sau cùng nằm trên cùng, nên khi lấy sách ta sẽ lấy cuốn đó trước. Đây chính là nguyên tắc vào sau ra trước.

Khai báo stack số nguyên:

#include <bits/stdc++.h>
using namespace std;

stack<int> st;

Ví dụ 1: push, top, pop

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;

    st.push(1);
    st.push(2);
    st.push(3);

    cout << st.top() << '\n'; // 3
    st.pop();
    cout << st.top() << '\n'; // 2

    return 0;
}

Ví dụ 2: empty và swap

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st, st2;

    for (int i = 1; i <= 4; i++)
        st.push(i);        // st = {1,2,3,4}

    cout << st.empty() << '\n'; // 0
    st.pop();                       // st = {1,2,3}
    cout << st.empty() << '\n'; // 0

    st2.swap(st); // st2 nhận các phần tử của st, st rỗng
    cout << st.empty() << '\n'; // 1

    return 0;
}

Đảo ngược dữ liệu

Đưa lần lượt phần tử vào stack, sau đó lấy ra sẽ thu được thứ tự ngược lại.

Kiểm tra dấu ngoặc

Gặp dấu mở thì push, gặp dấu đóng thì kiểm tra và pop. Nếu cuối cùng stack rỗng thì hợp lệ.

Biểu thức lồng nhau

Stack giúp xử lý các biểu thức có ngoặc, ví dụ tính khối lượng hóa chất dạng nén.

Stack đơn điệu

Dùng để giải bài toán nhìn thấy nhau, phần tử gần hơn/lớn hơn, hoặc tối ưu trên dãy.

Undo / quay lui

Các thao tác vừa thực hiện được lưu ở đỉnh stack để có thể hoàn tác ngược lại.

DFS không đệ quy

Stack có thể thay thế lời gọi đệ quy trong duyệt đồ thị hoặc cây.