Giải thích ngăn xếp dùng danh sách liên kết trong C

Tràn ngăn xếp và thiếu ngăn xếp có thể tránh bằng cấp phát bộ nhớ động.

Các thao tác trên ngăn xếp:

• Push (đẩy)
• Pop (lấy)

Push

Triển khai cơ bản danh sách liên kết:

&item = 10 
newnode = (node*) malloc(sizeof(node)); 
newnode->data = item; 
newnode->link = NULL; 
newnode->link = start; 
start = newnode;

Pop

Cú pháp:

Cú pháp

if(start == NULL) 
    printf("Khong the xoa. Danh sach rong") 
else{ 
    temp = start; 
    start = start->link; 
    free(temp); 
}

Chương trình

Chương trình C ngăn xếp bằng danh sách liên kết:

#include <stdio.h> 
#include <stdlib.h> 
struct node{ 
    int info; 
    struct node *ptr; 
} *top, *top1, *temp; 
int topelement(); 
void push(int data); 
void pop(); 
void empty(); 
void display(); 
void destroy(); 
void stack_count(); 
void create(); 
int count = 0; 
void main(){ 
    int no, ch, e; 
    printf("\n 1 - Push"); 
    printf("\n 2 - Pop"); 
    printf("\n 3 - Top"); 
    printf("\n 4 - Empty"); 
    printf("\n 5 - Exit"); 
    printf("\n 6 - Display"); 
    printf("\n 7 - Stack Count"); 
    printf("\n 8 - Destroy stack"); 
    create(); 
    while(1){ 
        printf("\n Nhap lua chon: "); 
        scanf("%d", &ch); 
        switch(ch){ 
            case 1: 
                printf("Nhap phan tu: "); 
                scanf("%d", &no); 
                push(no); 
                break; 
            case 2: 
                pop(); 
                break; 
            case 3: 
                if(top == NULL) 
                    printf("Ngan xep rong"); 
                else{ 
                    e = topelement(); 
                    printf("\n Phan tu dinh: %d", e); 
                } 
                break; 
            case 4: 
                empty(); 
                break; 
            case 5: 
                exit(0); 
            case 6: 
                display(); 
                break; 
            case 7: 
                stack_count(); 
                break; 
            case 8: 
                destroy(); 
                break; 
            default: 
                printf(" Lua chon sai: Thu lai "); 
                break; 
        } 
    } 
} 
// Khoi tao ngan xep rong 
void create(){ 
    top = NULL; 
} 
void stack_count(){ 
    printf("\n So phan tu ngan xep: %d", count); 
} 
// Push du lieu 
void push(int data){ 
    if(top == NULL){ 
        top = (struct node *)malloc(1*sizeof(struct node)); 
        top->ptr = NULL; 
        top->info = data; 
    } else { 
        temp = (struct node *)malloc(1*sizeof(struct node)); 
        temp->ptr = top; 
        temp->info = data; 
        top = temp; 
    } 
    count++; 
} 
void display(){ 
    top1 = top; 
    if(top1 == NULL){ 
        printf("Ngan xep rong"); 
        return; 
    } 
    while(top1 != NULL){ 
        printf("%d ", top1->info); 
        top1 = top1->ptr; 
    } 
} 
void pop(){ 
    top1 = top; 
    if(top1 == NULL){ 
        printf("\n Loi"); 
        return; 
    } else 
        top1 = top1->ptr; 
    printf("\n Gia tri Popped: %d", top->info); 
    free(top); 
    top = top1; 
    count--; 
} 
int topelement(){ 
    return(top->info); 
} 
// Kiem tra ngan xep rong 
void empty(){ 
    if(top == NULL) 
        printf("\n Ngan xep rong"); 
    else 
        printf("\n Ngan xep khong rong co %d gia tri", count); 
} 
void destroy(){ 
    top1 = top; 
    while(top1 != NULL){ 
        top1 = top->ptr; 
        free(top); 
        top = top1; 
        top1 = top1->ptr; 
    } 
    free(top1); 
    top = NULL; 
    printf("\n Tat ca da huy"); 
    count = 0; 
}

Đầu ra

Kết quả chạy chương trình:

1 - Push 
2 - Pop 
3 - Top 
4 - Empty 
5 - Exit 
6 - Display 
7 - Stack Count 
8 - Destroy stack 
Nhap lua chon: 1 
Nhap phan tu: 23 
Nhap lua chon: 1 
Nhap phan tu: 45 
Nhap lua chon: 1 
Nhap phan tu: 56 
Nhap lua chon: 2 
Popped: 56 
Nhap lua chon: 6 
45 23 
Nhap lua chon: 8 
Tat ca da huy 
Nhap lua chon: 6 
Ngan xep rong 
Nhap lua chon: 5