Stack - Cấu trúc dữ liệu LIFO

📖 Giới thiệu

Stack (ngăn xếp) là cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In, First Out) - phần tử cuối vào sẽ được lấy ra đầu tiên. Như một chồng đĩa, ta chỉ có thể thêm hoặc lấy đĩa từ đỉnh chồng.

Ví dụ đơn giản đầu tiên

cpp

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // Tạo stack
    stack<int> my_stack;
    
    // Thêm phần tử (push)
    my_stack.push(10);
    my_stack.push(20);
    my_stack.push(30);
    
    cout << "Stack có " << my_stack.size() << " phần tử" << endl;
    cout << "Phần tử trên đỉnh: " << my_stack.top() << endl;
    
    // Lấy phần tử ra (pop)
    while (!my_stack.empty()) {
        cout << "Lấy ra: " << my_stack.top() << endl;
        my_stack.pop();
    }
    
    return 0;
}

🔧 Cú pháp

Khai báo Stack

cpp

#include <stack>

stack<int> int_stack;                    // Stack số nguyên
stack<string> string_stack;             // Stack chuỗi
stack<int, vector<int>> vector_stack;   // Stack dựa trên vector
stack<int, deque<int>> deque_stack;     // Stack dựa trên deque (mặc định)

Các phương thức cơ bản

cpp

// Thêm/xóa
stack.push(value);          // Thêm phần tử lên đỉnh
stack.pop();                // Xóa phần tử trên đỉnh

// Truy cập
stack.top();                // Phần tử trên đỉnh (không xóa)

// Thông tin
stack.size();               // Số phần tử
stack.empty();              // Kiểm tra rỗng

// Lưu ý: Stack KHÔNG có iterator

🔬 Phân tích & Giải thích

Ứng dụng của Stack

1. Function Call Stack: Quản lý lời gọi hàm 2. Expression Evaluation: Tính toán biểu thức 3. Undo Operations: Hoàn tác thao tác 4. Backtracking: Thuật toán quay lui 5. Memory Management: Quản lý bộ nhớ

Stack vs Other Containers

Stack:

Chỉ truy cập được đỉnh
LIFO ordering
Không có iterators

Vector/Deque:

Random access
Flexible ordering
Full iterator support

💻 Ví dụ minh họa

Ví dụ 1: Calculator với Stack

cpp

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>
using namespace std;

class StackCalculator {
private:
    stack<double> operands;
    stack<char> operators;
    
    int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                return 0;
        }
    }
    
    bool is_operator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
    }
    
    double apply_operation(double a, double b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/':
                if (b == 0) {
                    throw runtime_error("Lỗi: Chia cho 0!");
                }
                return a / b;
            case '^': return pow(a, b);
            default:
                throw runtime_error("Toán tử không hợp lệ!");
        }
    }
    
    void process_operator(char op) {
        if (operands.size() < 2) {
            throw runtime_error("Không đủ toán hạng!");
        }
        
        double b = operands.top(); operands.pop();
        double a = operands.top(); operands.pop();
        
        double result = apply_operation(a, b, op);
        operands.push(result);
        
        cout << "Tính: " << a << " " << op << " " << b << " = " << result << endl;
    }
    
public:
    double evaluate_expression(const string& expression) {
        cout << "\n🧮 Tính toán biểu thức: " << expression << endl;
        cout << "Các bước tính toán:" << endl;
        
        // Clear stacks
        while (!operands.empty()) operands.pop();
        while (!operators.empty()) operators.pop();
        
        stringstream ss(expression);
        string token;
        
        while (ss >> token) {
            if (isdigit(token[0]) || (token[0] == '-' && token.length() > 1)) {
                // Số
                double num = stod(token);
                operands.push(num);
                cout << "Push số: " << num << endl;
            }
            else if (token[0] == '(') {
                operators.push('(');
                cout << "Push '('" << endl;
            }
            else if (token[0] == ')') {
                cout << "Xử lý ')'" << endl;
                while (!operators.empty() && operators.top() != '(') {
                    process_operator(operators.top());
                    operators.pop();
                }
                if (!operators.empty()) {
                    operators.pop(); // Remove '('
                }
            }
            else if (is_operator(token[0])) {
                char op = token[0];
                cout << "Xử lý toán tử: " << op << endl;
                
                while (!operators.empty() && 
                       operators.top() != '(' &&
                       precedence(operators.top()) >= precedence(op)) {
                    process_operator(operators.top());
                    operators.pop();
                }
                operators.push(op);
            }
        }
        
        // Xử lý các toán tử còn lại
        while (!operators.empty()) {
            process_operator(operators.top());
            operators.pop();
        }
        
        if (operands.size() != 1) {
            throw runtime_error("Biểu thức không hợp lệ!");
        }
        
        double result = operands.top();
        cout << "🎯 Kết quả cuối cùng: " << result << endl;
        return result;
    }
    
    void demo_calculator() {
        cout << "=== DEMO STACK CALCULATOR ===" << endl;
        
        vector<string> expressions = {
            "3 + 4 * 2",
            "( 3 + 4 ) * 2",
            "10 / 2 + 3 * 4",
            "2 ^ 3 + 4",
            "( 10 + 20 ) / ( 5 - 2 )"
        };
        
        for (const string& expr : expressions) {
            try {
                double result = evaluate_expression(expr);
                cout << "✅ " << expr << " = " << result << "\n" << endl;
            }
            catch (const exception& e) {
                cout << "❌ Lỗi: " << e.what() << "\n" << endl;
            }
        }
    }
};

int main() {
    StackCalculator calc;
    calc.demo_calculator();
    return 0;
}

Ví dụ 2: Browser History với Stack

cpp

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

class BrowserHistory {
private:
    stack<string> back_history;    // Lịch sử quay lại
    stack<string> forward_history; // Lịch sử tiến về phía trước
    string current_page;
    
public:
    BrowserHistory() {
        current_page = "about:blank";
        cout << "🌐 Khởi tạo trình duyệt" << endl;
        cout << "Trang hiện tại: " << current_page << endl;
    }
    
    void visit(const string& url) {
        if (!current_page.empty()) {
            back_history.push(current_page);
        }
        
        // Clear forward history khi visit trang mới
        while (!forward_history.empty()) {
            forward_history.pop();
        }
        
        current_page = url;
        cout << "🔗 Truy cập: " << current_page << endl;
        print_navigation_status();
    }
    
    void back() {
        if (back_history.empty()) {
            cout << "❌ Không thể quay lại - đã ở trang đầu tiên!" << endl;
            return;
        }
        
        forward_history.push(current_page);
        current_page = back_history.top();
        back_history.pop();
        
        cout << "⬅️ Quay lại: " << current_page << endl;
        print_navigation_status();
    }
    
    void forward() {
        if (forward_history.empty()) {
            cout << "❌ Không thể tiến tới - không có trang phía trước!" << endl;
            return;
        }
        
        back_history.push(current_page);
        current_page = forward_history.top();
        forward_history.pop();
        
        cout << "➡️ Tiến tới: " << current_page << endl;
        print_navigation_status();
    }
    
    void print_navigation_status() {
        cout << "📊 Trạng thái: Back(" << back_history.size() 
             << ") ← [" << current_page << "] → Forward(" 
             << forward_history.size() << ")" << endl;
    }
    
    void print_history() {
        cout << "\n📚 LỊCH SỬ DUYỆT WEB" << endl;
        cout << "===================" << endl;
        
        // In back history
        if (!back_history.empty()) {
            cout << "⬅️ Có thể quay lại:" << endl;
            stack<string> temp = back_history;
            vector<string> back_pages;
            
            while (!temp.empty()) {
                back_pages.push_back(temp.top());
                temp.pop();
            }
            
            for (int i = back_pages.size() - 1; i >= 0; i--) {
                cout << "  " << (back_pages.size() - i) << ". " << back_pages[i] << endl;
            }
        }
        
        // Trang hiện tại
        cout << "👉 Hiện tại: " << current_page << endl;
        
        // Forward history
        if (!forward_history.empty()) {
            cout << "➡️ Có thể tiến tới:" << endl;
            stack<string> temp = forward_history;
            vector<string> forward_pages;
            
            while (!temp.empty()) {
                forward_pages.push_back(temp.top());
                temp.pop();
            }
            
            for (int i = forward_pages.size() - 1; i >= 0; i--) {
                cout << "  " << (forward_pages.size() - i) << ". " << forward_pages[i] << endl;
            }
        }
        cout << "===================" << endl;
    }
    
    string get_current_page() const {
        return current_page;
    }
    
    bool can_go_back() const {
        return !back_history.empty();
    }
    
    bool can_go_forward() const {
        return !forward_history.empty();
    }
    
    void clear_history() {
        while (!back_history.empty()) back_history.pop();
        while (!forward_history.empty()) forward_history.pop();
        cout << "🗑️ Đã xóa toàn bộ lịch sử" << endl;
    }
};

void demo_browser_simulation() {
    cout << "=== DEMO BROWSER HISTORY SIMULATION ===" << endl;
    
    BrowserHistory browser;
    
    // Mô phỏng browsing session
    cout << "\n--- Phiên duyệt web ---" << endl;
    browser.visit("https://google.com");
    browser.visit("https://stackoverflow.com");
    browser.visit("https://github.com");
    browser.visit("https://cppreference.com");
    
    browser.print_history();
    
    // Test navigation
    cout << "\n--- Test navigation ---" << endl;
    browser.back();
    browser.back();
    browser.print_history();
    
    browser.forward();
    browser.print_history();
    
    // Visit new page (should clear forward history)
    cout << "\n--- Visit trang mới ---" << endl;
    browser.visit("https://leetcode.com");
    browser.print_history();
    
    // More navigation tests
    cout << "\n--- Test edge cases ---" << endl;
    browser.forward(); // Should fail
    
    for (int i = 0; i < 5; i++) {
        browser.back();
    }
    
    browser.print_history();
}

int main() {
    demo_browser_simulation();
    return 0;
}

Ví dụ 3: Undo/Redo System với Stack

cpp

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <memory>
using namespace std;

// Command interface
class Command {
public:
    virtual ~Command() = default;
    virtual void execute() = 0;
    virtual void undo() = 0;
    virtual string get_description() const = 0;
};

// Text document
class TextDocument {
private:
    string content;
    
public:
    void insert_text(int position, const string& text) {
        if (position >= 0 && position <= content.length()) {
            content.insert(position, text);
        }
    }
    
    void delete_text(int position, int length) {
        if (position >= 0 && position < content.length()) {
            content.erase(position, length);
        }
    }
    
    string get_content() const {
        return content;
    }
    
    void set_content(const string& new_content) {
        content = new_content;
    }
    
    void print() const {
        cout << "📄 Nội dung: \"" << content << "\"" << endl;
    }
};

// Insert command
class InsertCommand : public Command {
private:
    TextDocument* document;
    int position;
    string text;
    
public:
    InsertCommand(TextDocument* doc, int pos, const string& txt) 
        : document(doc), position(pos), text(txt) {}
    
    void execute() override {
        document->insert_text(position, text);
    }
    
    void undo() override {
        document->delete_text(position, text.length());
    }
    
    string get_description() const override {
        return "Insert \"" + text + "\" at position " + to_string(position);
    }
};

// Delete command
class DeleteCommand : public Command {
private:
    TextDocument* document;
    int position;
    int length;
    string deleted_text;
    
public:
    DeleteCommand(TextDocument* doc, int pos, int len) 
        : document(doc), position(pos), length(len) {
        // Save text before deletion for undo
        string content = document->get_content();
        if (pos >= 0 && pos < content.length()) {
            deleted_text = content.substr(pos, min(len, (int)content.length() - pos));
        }
    }
    
    void execute() override {
        document->delete_text(position, length);
    }
    
    void undo() override {
        document->insert_text(position, deleted_text);
    }
    
    string get_description() const override {
        return "Delete " + to_string(length) + " characters at position " + to_string(position);
    }
};

// Command manager with undo/redo stacks
class CommandManager {
private:
    stack<unique_ptr<Command>> undo_stack;
    stack<unique_ptr<Command>> redo_stack;
    TextDocument* document;
    
public:
    CommandManager(TextDocument* doc) : document(doc) {
        cout << "📋 Khởi tạo Command Manager" << endl;
    }
    
    void execute_command(unique_ptr<Command> command) {
        cout << "▶️ Thực hiện: " << command->get_description() << endl;
        
        command->execute();
        undo_stack.push(move(command));
        
        // Clear redo stack when new command is executed
        while (!redo_stack.empty()) {
            redo_stack.pop();
        }
        
        document->print();
        print_status();
    }
    
    void undo() {
        if (undo_stack.empty()) {
            cout << "❌ Không thể undo - không có command nào!" << endl;
            return;
        }
        
        auto command = move(undo_stack.top());
        undo_stack.pop();
        
        cout << "↶ Undo: " << command->get_description() << endl;
        command->undo();
        
        redo_stack.push(move(command));
        
        document->print();
        print_status();
    }
    
    void redo() {
        if (redo_stack.empty()) {
            cout << "❌ Không thể redo - không có command nào!" << endl;
            return;
        }
        
        auto command = move(redo_stack.top());
        redo_stack.pop();
        
        cout << "↷ Redo: " << command->get_description() << endl;
        command->execute();
        
        undo_stack.push(move(command));
        
        document->print();
        print_status();
    }
    
    void print_status() {
        cout << "📊 Trạng thái: Undo(" << undo_stack.size() 
             << ") | Redo(" << redo_stack.size() << ")" << endl;
    }
    
    void print_history() {
        cout << "\n📚 LỊCH SỬ COMMANDS" << endl;
        cout << "==================" << endl;
        
        if (!undo_stack.empty()) {
            cout << "↶ Có thể undo:" << endl;
            // Note: Stack doesn't allow iteration, so we can't print details
            cout << "  " << undo_stack.size() << " commands available" << endl;
        }
        
        if (!redo_stack.empty()) {
            cout << "↷ Có thể redo:" << endl;
            cout << "  " << redo_stack.size() << " commands available" << endl;
        }
        
        if (undo_stack.empty() && redo_stack.empty()) {
            cout << "Không có lịch sử commands" << endl;
        }
        cout << "==================" << endl;
    }
    
    bool can_undo() const {
        return !undo_stack.empty();
    }
    
    bool can_redo() const {
        return !redo_stack.empty();
    }
};

void demo_text_editor() {
    cout << "=== DEMO TEXT EDITOR WITH UNDO/REDO ===" << endl;
    
    TextDocument document;
    CommandManager manager(&document);
    
    document.print();
    
    // Sequence of edits
    cout << "\n--- Editing session ---" << endl;
    manager.execute_command(make_unique<InsertCommand>(&document, 0, "Hello"));
    manager.execute_command(make_unique<InsertCommand>(&document, 5, " World"));
    manager.execute_command(make_unique<InsertCommand>(&document, 11, "!"));
    manager.execute_command(make_unique<DeleteCommand>(&document, 5, 6)); // Delete " World"
    manager.execute_command(make_unique<InsertCommand>(&document, 5, " C++"));
    
    manager.print_history();
    
    // Test undo/redo
    cout << "\n--- Undo operations ---" << endl;
    manager.undo();
    manager.undo();
    manager.undo();
    
    cout << "\n--- Redo operations ---" << endl;
    manager.redo();
    manager.redo();
    
    // New operation after undo (should clear redo stack)
    cout << "\n--- New operation after undo ---" << endl;
    manager.execute_command(make_unique<InsertCommand>(&document, 5, " Programming"));
    
    manager.print_history();
    
    // Edge case tests
    cout << "\n--- Edge case tests ---" << endl;
    manager.redo(); // Should fail
    
    // Undo all
    while (manager.can_undo()) {
        manager.undo();
    }
    
    manager.undo(); // Should fail
}

int main() {
    demo_text_editor();
    return 0;
}

🏋️ Thực hành

Bài tập 1: Balanced Parentheses Checker

Tạo function check_balanced_parentheses() sử dụng stack để:

Kiểm tra dấu ngoặc cân bằng: (), [], {}
Báo lỗi vị trí ngoặc không khớp
Hỗ trợ nhiều loại ngoặc

Bài tập 2: Function Call Stack Monitor

Tạo class CallStackMonitor để:

Theo dõi lời gọi hàm
Hiển thị call stack hiện tại
Detect stack overflow

Bài tập 3: Tower of Hanoi

Implement Tower of Hanoi game với:

3 stacks đại diện cho 3 cọc
Validation di chuyển hợp lệ
Tự động solve algorithm

📋 Tóm tắt

Stack: LIFO data structure - Last In, First Out
Operations:
- push(): Thêm lên đỉnh O(1)
- pop(): Xóa khỏi đỉnh O(1)
- top(): Xem đỉnh O(1)
- empty(), size(): Kiểm tra trạng thái O(1)
Ứng dụng:
- Function call management
- Expression evaluation
- Undo/Redo systems
- Backtracking algorithms
- Memory management
Khi nào dùng:
- Cần LIFO ordering
- Temporary storage
- Recursive problem solving
- State management

Bài tiếp theo: Queue - Tìm hiểu về FIFO data structure.

Stack - Cấu trúc dữ liệu LIFO ​

📖 Giới thiệu ​

Ví dụ đơn giản đầu tiên ​

🔧 Cú pháp ​

Khai báo Stack ​

Các phương thức cơ bản ​

🔬 Phân tích & Giải thích ​

Ứng dụng của Stack ​

Stack vs Other Containers ​

💻 Ví dụ minh họa ​

Ví dụ 1: Calculator với Stack ​

Ví dụ 2: Browser History với Stack ​

Ví dụ 3: Undo/Redo System với Stack ​

🏋️ Thực hành ​

Bài tập 1: Balanced Parentheses Checker ​

Bài tập 2: Function Call Stack Monitor ​

Bài tập 3: Tower of Hanoi ​

📋 Tóm tắt ​