Chương trình C++ triển khai ngăn xếp (Stack) bằng danh sách liên kết

Ngăn xếp (Stack) tuân theo cơ chế LIFO (Last In First Out) - phần tử đẩy vào sau được lấy ra trước. Các phép toán chính: Push (thêm), Pop (lấy ra), Peek (xem đỉnh).

Ví dụ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};

struct Node* top = NULL;

void push(int val) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}

void pop() {
    if (top == NULL)
        cout << "Stack Underflow" << endl;
    else {
        cout << "The popped element is " << top->data << endl;
        top = top->next;
    }
}

void display() {
    struct Node* ptr;
    if (top == NULL)
        cout << "stack is empty";
    else {
        ptr = top;
        cout << "Stack elements are: ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}

int main() {
    int ch, val;
    cout << "1) Push in stack" << endl;
    cout << "2) Pop from stack" << endl;
    cout << "3) Display stack" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter choice: " << endl;
        cin >> ch;
        switch(ch) {
            case 1: {
                cout << "Enter value to be pushed: " << endl;
                cin >> val;
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                display();
                break;
            }
            case 4: {
                cout << "Exit" << endl;
                break;
            }
            default: {
                cout << "Invalid Choice" << endl;
            }
        }
    } while(ch != 4);
    return 0;
}

Kết quả

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit
Enter choice: 1
Enter value to be pushed: 2
Enter choice: 1
Enter value to be pushed: 6
Enter choice: 1
Enter value to be pushed: 8
Enter choice: 1
Enter value to be pushed: 7
Enter choice: 2
The popped element is 7
Enter choice: 3
Stack elements are: 8 6 2
Enter choice: 5
Invalid Choice
Enter choice: 4
Exit

Cấu trúc Node

struct Node {
    int data;
    struct Node *next;
};

Hàm push()

Tạo nút mới, gán giá trị, trỏ next về top hiện tại, cập nhật top = newnode.

void push(int val) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}

Hàm pop()

Nếu rỗng → Underflow. Ngược lại in phần tử top, di chuyển top = top->next.

void pop() {
    if (top == NULL)
        cout << "Stack Underflow" << endl;
    else {
        cout << "The popped element is " << top->data << endl;
        top = top->next;
    }
}

Hàm display()

Duyệt từ top đến cuối danh sách bằng con trỏ ptr.

void display() {
    struct Node* ptr;
    if (top == NULL)
        cout << "stack is empty";
    else {
        ptr = top;
        cout << "Stack elements are: ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}

Hàm main() - Menu

int main() {
    int ch, val;
    cout << "1) Push in stack" << endl;
    cout << "2) Pop from stack" << endl;
    cout << "3) Display stack" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter choice: " << endl;
        cin >> ch;
        switch(ch) {
            case 1: {
                cout << "Enter value to be pushed: " << endl;
                cin >> val;
                push(val);
                break;
            }
            case 2: pop(); break;
            case 3: display(); break;
            case 4: cout << "Exit" << endl; break;
            default: cout << "Invalid Choice" << endl;
        }
    } while(ch != 4);
    return 0;
}