🎯 Bài giảng: Cấu trúc dữ liệu Stack (Ngăn xếp)

Stack là một trong những cấu trúc dữ liệu cơ bản nhất, được dùng rộng rãi trong thuật toán và rất gần gũi với đời sống (chồng sách, đĩa, khay cốc...).

I. Giới thiệu & Ví dụ thực tế

Hình dung bạn xếp chồng sách. Muốn lấy sách ở trên cùng bạn phải nhấc quyển vừa đặt gần nhất. Đó là nguyên lý LIFO – Last In, First Out (vào sau, ra trước).

Nguyên tắc LIFO – “vào sau ra trước”.

II. Lý thuyết cơ bản

• Push(x): thêm phần tử x vào đỉnh.
• Pop(): lấy phần tử ở đỉnh ra khỏi stack.
• Top(): xem (không xoá) phần tử ở đỉnh.
• Empty(): kiểm tra rỗng.
• Size(): số lượng phần tử hiện có.

#include 
#include 
using namespace std;
int main() {
    stack st;
    st.push(10);
    st.push(20);
    cout << st.top() << "
"; // 20
    st.pop();                     // xoá 20
    cout << st.size() << "
";   // 1
}

III. Trình mô phỏng Stack: hình ảnh + mô tả từng dòng lệnh

Trong mô phỏng dưới đây, giao diện được chia làm 3 cột:

• 🖱 Cột 1 – Thao tác: Các nút mô phỏng hành động của người lập trình (Push, Pop, Top, Size, Reset).
• 💻 Cột 2 – Dòng lệnh tương ứng: Mỗi thao tác sẽ tô sáng các dòng lệnh C++ mà máy tính thực hiện.
• 📊 Cột 3 – Kết quả minh hoạ: Stack hiển thị theo thời gian thực sau khi lệnh được chạy.

VI. Khi nào dùng Stack & Cách nhận biết bài toán cần Stack

Stack được gắn tag cho những bài toán mà thứ tự xử lý dữ liệu phụ thuộc vào nguyên tắc “vào sau ra trước” hoặc khi ta cần ghi nhớ tạm thời các trạng thái để quay lại sau. Dưới đây là các nhóm bài toán phổ biến sử dụng Stack, kèm lý do và ví dụ.

💡 Tóm lại: Hễ bài toán cần “ghi nhớ tạm thời để quay lại”, “đảo ngược thứ tự”, hoặc “đóng–mở cặp” theo quy luật → gần như chắc chắn có thể giải bằng Stack.

V. Hệ thống bài tập theo cấp độ (có giải thích chi tiết)

📘 Egg

#include 
#include 
using namespace std;
int main(){
    string s; cin >> s;
    stack st;
    for(char c : s) st.push(c);
    while(!st.empty()){ cout << st.top(); st.pop(); }
}

#include 
#include 
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long x,sum=0; cin>>n;
    stack st;
    for(int i=0;i>x; st.push(x);}
    while(!st.empty()){ sum+=st.top(); st.pop(); }
    cout<

#include 
using namespace std;
bool match(char o, char c){
    return (o=='('&&c==')')||(o=='['&&c==']')||(o=='{'&&c=='}')||(o=='<'&&c=='>');
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s; cin>>s;
    stack st;
    for(char c : s){
        if(c=='('||c=='['||c=='{'||c=='<') st.push(c);
        else {
            if(st.empty() || !match(st.top(), c)) return cout<<"NO",0;
            st.pop();
        }
    }
    cout<<(st.empty()?"YES":"NO");
}

#include 
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s, w; getline(cin, s);
    stack st;
    stringstream ss(s);
    while(ss>>w) st.push(w);
    bool first=true;
    while(!st.empty()){
        if(!first) cout<<' ';
        cout<

#include 
using namespace std;
bool isNumber(const string &t){
    if(t.empty()) return false;
    int i=0; if(t[0]=='-'||t[0]=='+') i=1;
    for(;i<(int)t.size();++i) if(!isdigit(t[i])) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s; getline(cin, s);
    stringstream ss(s); string tok;
    stack st;
    while(ss>>tok){
        if(isNumber(tok)) st.push(stoll(tok));
        else{
            long long b=st.top(); st.pop();
            long long a=st.top(); st.pop();
            if(tok=="+") st.push(a+b);
            else if(tok=="-") st.push(a-b);
            else if(tok=="*") st.push(a*b);
            else if(tok=="/") st.push(a/b); // giả sử b != 0, chia số nguyên
        }
    }
    cout<

#include 
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n; vector a(n), ans(n, -1);
    for(int i=0;i>a[i];
    stack st;
    for(int i=0;i a[st.top()]){
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0;i':' ');
}