Khái niệm Stack (Ngăn xếp) trong ngôn ngữ C

Cấu trúc dữ liệu là tập hợp dữ liệu tổ chức có cấu trúc. Phân làm hai loại:

• Cấu trúc tuyến tính: dữ liệu tổ chức tuyến tính. VD: mảng, cấu trúc, stack, queue, danh sách liên kết.
• Cấu trúc phi tuyến tính: tổ chức phân cấp. VD: cây, đồ thị, tập hợp, bảng.

Stack trong C

Là cấu trúc tuyến tính, chèn và xóa chỉ ở một đầu (đỉnh - top).

Các thao tác cơ bản

• Push – Thêm phần tử vào stack.
• Pop – Xóa phần tử khỏi stack.

Các tình trạng

• Stack Overflow – Thêm vào stack đã đầy.
• Stack Underflow – Xóa từ stack rỗng.

Thuật toán

Push()

if (top == n-1) printf("Stack overflow");
else {
    top++;
    a[top] = item;
}

Pop()

if (top == -1) printf("Stack underflow");
else {
    item = a[top];
    top--;
}

Display()

if (top == -1) printf("Stack rong");
else {
    for (i = 0; i <= top; i++)
        printf("%d ", a[i]);
}

Chương trình triển khai Stack bằng mảng

#include <stdio.h>
#include <stdlib.h>

#define MAX 100
int top = -1, n;
int a[MAX];

void push() {
    int item;
    if (top == n-1)
        printf("Stack overflow\n");
    else {
        printf("Nhap phan tu can chen: ");
        scanf("%d", &item);
        top++;
        a[top] = item;
    }
}

void pop() {
    if (top == -1)
        printf("Stack underflow\n");
    else {
        printf("Phan tu xoa = %d\n", a[top]);
        top--;
    }
}

void display() {
    if (top == -1)
        printf("Stack rong\n");
    else {
        printf("Noi dung stack: ");
        for (int i = 0; i <= top; i++)
            printf("%d ", a[i]);
        printf("\n");
    }
}

int main() {
    int ch;
    printf("Nhap kich thuoc stack: ");
    scanf("%d", &n);
    printf("1. Push\n2. Pop\n3. Hien thi\n4. Thoat\n");
    do {
        printf("Lua chon: ");
        scanf("%d", &ch);
        switch(ch) {
            case 1: push(); display(); break;
            case 2: pop(); display(); break;
            case 3: display(); break;
            case 4: exit(0);
            default: printf("Lua chon khong hop le\n");
        }
    } while(ch != 4);
    return 0;
}

Kết quả mẫu

Nhap kich thuoc stack: 5
1. Push
2. Pop
3. Hien thi
4. Thoat
Lua chon: 1
Nhap phan tu can chen: 10
Noi dung stack: 10
Lua chon: 1
Nhap phan tu can chen: 20
Noi dung stack: 10 20
Lua chon: 2
Phan tu xoa = 20
Noi dung stack: 10
Lua chon: 4