Chương trình C++ triển khai ngăn xếp (Stack)

Trong chương trình này, chúng ta sẽ thấy cách triển khai ngăn xếp (stack) bằng C++. Ngăn xếp là một cấu trúc dữ liệu trừu tượng chứa một tập hợp các phần tử. Ngăn xếp thực hiện cơ chế LIFO (Last In First Out) tức là phần tử được đẩy vào sau cùng sẽ được lấy ra đầu tiên. Một số hoạt động chính trong ngăn xếp bao gồm:

• Push - Thêm một giá trị dữ liệu vào đỉnh ngăn xếp.

• Pop - Loại bỏ giá trị dữ liệu ở đỉnh ngăn xếp.

• Peek - Trả về giá trị dữ liệu ở đỉnh ngăn xếp.

Một chương trình triển khai ngăn xếp sử dụng mảng được đưa ra như sau.

Đầu vào: Push các phần tử 11, 22, 33, 44, 55, 66 
Đầu ra: Pop các phần tử 66, 55, 44, 33, 22, 11

Thuật toán

push(item)

Bắt đầu
    Tăng con trỏ top lên 1
    Chèn item vào vị trí top
Kết thúc

pop()

Bắt đầu
    item = phần tử đỉnh từ ngăn xếp
    Giảm con trỏ top xuống 1
    Trả về item
Kết thúc

peek()

Bắt đầu
    item = phần tử đỉnh từ ngăn xếp
    Trả về item
Kết thúc

Mã ví dụ

#include <iostream> 
using namespace std; 

int stack[100], n = 100, top = -1; 

void push(int val) { 
    if(top >= n-1) 
        cout << "Stack Overflow" << endl; 
    else { 
        top++; 
        stack[top] = val; 
    } 
} 

void pop() { 
    if(top <= -1) 
        cout << "Stack Underflow" << endl; 
    else { 
        cout << "Phần tử bị lấy ra là " << stack[top] << endl; 
        top--; 
    } 
} 

void display() { 
    if(top >= 0) { 
        cout << "Các phần tử trong stack: "; 
        for(int i = top; i >= 0; i--) 
            cout << stack[i] << " "; 
        cout << endl; 
    } else 
        cout << "Stack rỗng"; 
} 

int main() { 
    int ch, val; 
    cout << "1) Push vào stack" << endl; 
    cout << "2) Pop từ stack" << endl; 
    cout << "3) Hiển thị stack" << endl; 
    cout << "4) Thoát" << endl; 
    do { 
        cout << "Nhập lựa chọn: " << endl; 
        cin >> ch; 
        switch(ch) { 
            case 1: { 
                cout << "Nhập giá trị cần push: " << endl; 
                cin >> val; 
                push(val); 
                break; 
            } 
            case 2: { 
                pop(); 
                break; 
            } 
            case 3: { 
                display(); 
                break; 
            } 
            case 4: { 
                cout << "Thoát" << endl; 
                break; 
            } 
            default: { 
                cout << "Lựa chọn không hợp lệ" << endl; 
            } 
        } 
    } while(ch != 4); 
    return 0; 
}

Kết quả

1) Push vào stack 
2) Pop từ stack 
3) Hiển thị stack 
4) Thoát 
Nhập lựa chọn: 1 
Nhập giá trị cần push: 2 
Nhập lựa chọn: 1 
Nhập giá trị cần push: 6 
Nhập lựa chọn: 1 
Nhập giá trị cần push: 8 
Nhập lựa chọn: 1 
Nhập giá trị cần push: 7 
Nhập lựa chọn: 2 
Phần tử bị lấy ra là 7 
Nhập lựa chọn: 3 
Các phần tử trong stack: 8 6 2 
Nhập lựa chọn: 5 
Lựa chọn không hợp lệ 
Nhập lựa chọn: 4 
Thoát