Ngăn xếp (Stack) trong C++

Stack và 3 dạng ký pháp biểu thức:

1. Infix (trung tố): toán tử nằm giữa 2 toán hạng

   • Ví dụ: A + B

   • Đây là cách viết thông thường chúng ta hay dùng.

   • Vấn đề: phải quan tâm độ ưu tiên toán tử và dấu ngoặc khi tính toán.

2. Prefix (tiền tố, còn gọi là Polish Notation): toán tử nằm trước toán hạng

   • Ví dụ: + A B

   • Ưu điểm: không cần dấu ngoặc, vì thứ tự tính toán đã xác định rõ ràng.

3. Postfix (hậu tố, còn gọi là Reverse Polish Notation – RPN): toán tử nằm sau toán hạng

   • Ví dụ: A B +

   • Ưu điểm: giống Prefix, không cần dấu ngoặc.

Ứng dụng của stack trong các dạng ký pháp

1. Chuyển đổi biểu thức

   • Stack được dùng để chuyển từ Infix → Postfix hoặc Infix → Prefix, để thuận tiện cho máy tính xử lý.

   • Ví dụ: biểu thức A + B * C (infix) → A B C * + (postfix).

2. Đánh giá biểu thức (expression evaluation)

   • Máy tính dễ dàng tính toán với postfix hoặc prefix bằng cách dùng stack.

   • Ví dụ: postfix A B + C *

     • Đọc từ trái sang: push A, push B, gặp + → pop A và B ra tính A+B, push kết quả.

     • Tiếp tục với C, gặp * → pop (A+B) và C, tính (A+B)*C.

3. Ứng dụng trong ngôn ngữ lập trình và compiler

   • Trình biên dịch thường chuyển đổi infix → postfix/prefix để máy thực thi.

   • Máy tính khi thực hiện phép toán cũng ưu tiên dùng postfix (RPN) để tránh phải xử lý dấu ngoặc và độ ưu tiên.

👉 Tóm lại:

• Infix: tiện cho con người đọc.

• Prefix/Postfix: tiện cho máy tính xử lý.

• Stack: là cấu trúc dữ liệu then chốt để chuyển đổi và tính toán các biểu thức này.

Stack là một cấu trúc dữ liệu theo nguyên tắc LIFO (Last In, First Out), nghĩa là phần tử được thêm vào sau cùng sẽ được lấy ra đầu tiên. Trong C++, Stack được hỗ trợ bởi thư viện chuẩn STL (Standard Template Library).

Các lệnh cơ bản trong Stack:

1. push(element): Thêm một phần tử vào đỉnh của stack.

   • Độ phức tạp: O(1)

2. pop(): Loại bỏ phần tử ở đỉnh của stack.

   • Độ phức tạp: O(1)

3. top(): Truy cập phần tử ở đỉnh của stack mà không loại bỏ nó.

   • Độ phức tạp: O(1)

4. empty(): Kiểm tra xem stack có rỗng không.

   • Độ phức tạp: O(1)

5. size(): Trả về số lượng phần tử trong stack.

   • Độ phức tạp: O(1)

6. swap(stack& other): Hoán đổi nội dung của stack hiện tại với một stack khác.

   • Độ phức tạp: O(1)

Ví dụ minh họa về cách sử dụng stack trong C++:

#include <iostream>
#include <stack>

using namespace std;

int main() {
    // Khai báo stack chứa các số nguyên
    stack<int> myStack;

    // Thêm các phần tử vào stack
    myStack.push(10);  // [10]
    myStack.push(20);  // [10, 20]
    myStack.push(30);  // [10, 20, 30]

    // In ra kích thước của stack: 3
    cout << "Size of stack: " << myStack.size() << endl;

    // Truy cập phần tử ở đỉnh của stack: 30
    cout << "Top element: " << myStack.top() << endl;

    // Loại bỏ phần tử ở đỉnh của stack
    myStack.pop();     // [10, 20]

    // Truy cập phần tử ở đỉnh của stack: 20
    cout << "Top element after pop: " << myStack.top() << endl;

    // Kiểm tra stack có rỗng không
    if (myStack.empty()) {
        cout << "Stack is empty." << endl;
    } else {
        cout << "Stack is not empty." << endl;
    }

    // Khai báo hai stack chứa các số nguyên
    stack<int> stack1;
    stack<int> stack2;

    // Thêm các phần tử vào stack1
    stack1.push(10);
    stack1.push(20);
    stack1.push(30);

    // Thêm các phần tử vào stack2
    stack2.push(100);
    stack2.push(200);

    // Trước khi hoán đổi
    cout << "Stack1 top before swap: " << stack1.top() << endl; // Output: 30
    cout << "Stack2 top before swap: " << stack2.top() << endl; // Output: 200

    // Hoán đổi nội dung của stack1 và stack2
    stack1.swap(stack2);

    // Sau khi hoán đổi
    cout << "Stack1 top after swap: " << stack1.top() << endl; // Output: 200
    cout << "Stack2 top after swap: " << stack2.top() << endl; // Output: 30

    return 0;
}