堆栈的那些事儿

柔情只为你懂 2022-05-27 07:55 283阅读 0赞

#### 前言 ####

前面聊了线性表，这次来聊一些非常重要的数据结构——堆栈。关于堆栈，我们可以理解为我们在使用浏览器的浏览网页的时候，我们点击返回按钮的时候总是返回到我们最近一次浏览的网页，而不是我们最开始浏览的网页。另外我们可以用厨房的盘子来比喻，我们需要使用盘子的时候是用最上面的盘子，我们用好以后放回去，也总是放在最上面，这些都是堆栈，其主要特点就是先进后出。对于其实现方法，我们仍然通过数组实现和链表实现的方式。

#### 数组实现 ####

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 5
    // 定义堆栈结构体
    typedef struct stack {
        int data[MAX];
        int count;
    } Stack;
    // 初始化
    void init(Stack *p) {
        p -> count = 0;
    }
    // 是否堆栈已经满了
    int isFull(Stack *p) {
        return p -> count > MAX-1;
    }
    // 入栈
    void push(Stack *p, int data) {
        if(isFull((p)))
            printf("堆栈已经满了,%d入栈失败\n", data);
        else
            p -> data[p -> count++] = data;
    }
    // 堆栈是否为空
    int isEmpty(Stack *p) {
        return p -> count;
    }
    // 出栈
    int pop(Stack *p) {
        return p -> data[--p->count];
    }
    int main() {
        Stack s;
        init(&s);
        for(int i=0; i<6; i++)
            push(&s, i);
        while(isEmpty(&s))
            printf("%d ", pop(&s));
        printf("\n");
        return 0;
    }

#### 链表实现 ####

#include<stdio.h>
    #include<stdlib.h>
    typedef struct node {
        int data;
        struct node *next;
    } Node;
    // 定义堆栈结构体
    typedef struct stack {
        Node *top;
    } Stack;
    // 初始化
    void init(Stack *p) {
        p -> top = NULL;
    }
    // 入栈
    void push(Stack *p, int data) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode -> data = data;
        newNode -> next = p -> top;
        p -> top = newNode;
    }
    // 堆栈是否为空
    int isEmpty(Stack *p) {
        return p -> top;
    }
    // 出栈
    int pop(Stack *p) {
        int data;
        Node *t = p -> top;
        p -> top = t -> next;
        data = t -> data;
        free(t);
        return data;
    }
    int main() {
        Stack s;
        init(&s);
        for(int i=0; i<6; i++)
            push(&s, i);
        while(isEmpty(&s))
            printf("%d ", pop(&s));
        printf("\n");
        return 0;
    }