C++: Stack

Tổng quan

Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên tắc Last In First Out (LIFO). Điều này có thể hiểu đơn giản là phần tử nào được thêm vào sau cùng sẽ được lấy ra đầu tiên. Trong đó một phần tử mới được thêm vào ở một đầu (trên cùng) và một phần tử chỉ bị xóa khỏi đầu đó. Một liên tưởng thực tế có thể nghĩ đến là khi xếp một chồng sách, cuốn sách trên cùng có thể được lấy ra một cách dễ dàng.

Sử dụng stack bằng thư viện STL

Thư viện mẫu chuẩn (STL) cung cấp sẵn một template cho việc sử dụng stack.

Khai báo thư viện

#include <stack>

Khởi tạo một stack rỗng

Stack được triển khai dưới dạng template, cho phép  tạo stack có thể chứa các kiểu dữ liệu khác nhau. Tuy nhiên, mỗi instance của stack chỉ chứa duy nhất một kiểu dữ liệu cụ thể.

Cú pháp: std::stack<kiểu dữ liệu> {tên stack}

std::stack<int> intStack;
std::stack<std::string> stringStack;
std::stack<double> doubleStack;

Có thể sử dụng namespace std để khai báo ngắn gọn hơn

using namespace std;

stack<int> intStack;
stack<std::string> stringStack;
stack<double> doubleStack;

Các hàm cơ bản được hỗ trợ

empty() – Trả về xem ngăn xếp có trống không – Độ phức tạp thời gian : O(1) 
size() – Trả về kích thước của ngăn xếp – Độ phức tạp thời gian : O(1) 
top() – Trả về một tham chiếu lên phần tử trên cùng của ngăn xếp – Độ phức tạp thời gian : O(1) 
push(g) – Thêm phần tử 'g' ở đầu ngăn xếp – Độ phức tạp thời gian : O(1) 
pop() – Xóa phần tử được nhập gần đây nhất phần tử của ngăn xếp – Độ phức tạp thời gian: O(1)

Ví dụ

#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stack;
stack.push(21);// The values pushed in the stack should be of the same data which is written during declaration of stack
stack.push(22);
stack.push(24);
stack.push(25); // 25 là phần tử trên cùng

cout << stack.top() << endl; // output 25
stack.pop(); // xóa phần tử trên cùng của stack (lúc này stack gồm 21, 22, 24)

while (!stack.empty()) { // lặp đến khi stack rỗng
cout << stack.top() <<" "; // in ra phần tử trên cùng
stack.pop(); // xóa phần tử trên cùng
}
// output : 24 22 21
}

Tự định nghĩa stack bằng mảng

Có thể cài đặt stack một cách đơn giản bằng cách sử dụng một mảng và một biến topIndex là index đại diện của phần tử trên cùng của stack. Khi thêm một phần tử mới vào stack, tăng biến topIndex lên 1 và gán giá trị của mảng tại vị trí topIndex bằng phần tử vừa thêm vào. Khi muốn xóa phần tử trên cùng, chỉ việc giảm biến topIndex đi 1.

#include <iostream>

template <typename T, int MAX_SIZE>
class Stack {
private:
    T arr[MAX_SIZE];
    int topIndex;

public:
    Stack() : topIndex(-1) {}

    bool isEmpty() {
        return (topIndex == -1);
    }

    bool isFull() {
        return (topIndex == MAX_SIZE - 1);
    }

    void push(T value) {
        if (isFull()) {
            std::cout << "Stack is full. Cannot push " << value << std::endl;
            return;
        }
        arr[++topIndex] = value;
    }

    void pop() {
        if (isEmpty()) {
            std::cout << "Stack is empty. Cannot pop" << std::endl;
            return;
        }
        --topIndex;
    }

    T top() {
        if (isEmpty()) {
            std::cout << "Stack is empty. No top element" << std::endl;
            return T();
        }
        return arr[topIndex];
    }
};

int main() {
    Stack<int, 5> intStack;
    Stack<char, 10> charStack;

    intStack.push(10);
    intStack.push(20);
    intStack.push(30);

    charStack.push('A');
    charStack.push('B');
    charStack.push('C');

    std::cout << "Top of intStack: " << intStack.top() << std::endl; // In ra: Top of intStack: 30
    std::cout << "Top of charStack: " << charStack.top() << std::endl; // In ra: Top of charStack: C

    intStack.pop();
    charStack.pop();

    std::cout << "After pop operations:" << std::endl;
    std::cout << "Top of intStack: " << intStack.top() << std::endl; // In ra: Top of intStack: 20
    std::cout << "Top of charStack: " << charStack.top() << std::endl; // In ra: Top of charStack: B

    return 0;
}

Output:
Top of intStack: 30
Top of charStack: C
After pop operations:
Top of intStack: 20
Top of charStack: B

Lưu ý

Khi cài đặt stack bằng mảng, ta có thể truy cập ngẫu nhiên vào bất cứ phần tử nào, khác với stack được cung cấp sẵn bởi thư viện mẫu chuẩn STL (chỉ có thể làm việc với phân tử cuối cùng). Do đó, nếu vì lý do gì đó cần truy cập nhiều hơn 1 phần tử ở cuối thì nên dùng stack tự xây dựng. Ngoài ra có thể sử dụng vector trong C++ như một stack khi vector cung cấp tính linh hoạt cao về kích thước và loại dữ liệu có thể lưu trữ, kèm theo nhiều phương thức hữu ích như empty(), size(), back() (tương đương với top() của stack), push_back(), và pop_back(). Vector cũng có thể tự động thay đổi kích thước khi cần thiết (Dynamic Resizing) và cũng có thể hỗ trợ truy cập ngẫu nhiên.