栈的基本概念

栈是一种特殊的线性存储结构，是一种操作受到限制的线性表，特殊体现在两个地方：

1、元素进栈出栈的操作只能从同一端完成，另一端是封闭的，通常将数据进栈叫做入栈，压栈等，出栈叫做弹栈、出栈等。

2、栈中无论存数据还是取数据，都必须遵循“先进后出”的原则，即最先入栈的元素最先出栈。以上图为例，很容易可以看出是元素 1 最先入栈，然后依次是元素 2、3、4 入栈。在此基础上，如果想取出元素 1，根据“先进后出”的原则，必须先依次将元素 4、3、2 出栈，最后才能轮到元素 1 出栈。

由此我们可以对栈存储结构下一个定义：栈是一种“只能从一端存取元素，且存取过程必须遵循‘先进后出’原则”的线性存储结构。

栈就类似于弹夹，只能从一端压入子弹，要取出子弹也只能对最上方的子弹进行操作，对应了栈先进后出，只能操作栈顶元素。

上述提到，栈本质上是操作受到限制的线性表，线性表主要有两种：分别是数组和链表，所以栈有数组和链表两种实现方式。

1.顺序存储的数组，优点: 节省空间，操作简单，学习成本较低，易于理解。缺点: 栈的大小从一开始就固定了，不利于动态扩容。

2.非顺序存储的链表，优缺点：与数组栈正好相反。

栈的核心操作包括出栈，入栈，判空，访问栈顶等，数组栈要比链表栈多一个判满操作。

数组栈

下述代码实现了栈的基本操作，包括出栈、入栈、判空、判满、访问栈顶。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
//数组栈要提前设置最大容量
#define max 20typedef struct
{//以int类型数据为例int data[max];int index;//栈顶地址
}stack;
//压栈
bool stack_push(stack *sk,int data)
{//检测空指针if(sk == NULL)return false;//检测栈是否已满if(sk->index == max - 1)return false;//更新栈顶地址sk->index++;//数据入栈sk->data[sk->index] = data;return true;
}
//弹栈
bool stack_pop(stack *sk)
{//检测空指针if(sk == NULL)return false;//检测栈是否已空if(sk->index < 0)return false;//更新栈顶地址，无需将后面的数据置0，因为操作受限制，无法访问到后边的下标。sk->index--;return true;
}
//返回栈顶元素
int stack_top(stack *sk)
{//检测空指针if(sk == NULL)return false;//检测栈是否已空if(sk->index < 0)return false;return sk->data[sk->index];
}
bool stack_full(stack *sk)
{if(sk == NULL)return false;return sk->index == max - 1 ? true : false;
}
//查看栈是否已空
bool stack_empty(stack *sk)
{//检测空指针if(sk == NULL)return false;return sk->index < 0 ? true : false;
}int main(int argc, char const *argv[])
{//初始化栈，设置栈顶为-1stack sk;sk.index = -1;//逐个压栈，查看栈顶元素for (int i = 0; i < 20; i++){stack_push(&sk,i + 1);printf("%d ",stack_top(&sk));}printf("\n");stack_full(&sk) ? printf("已满\n") : printf("未满\n");stack_empty(&sk) ? printf("空\n") : printf("非空\n");stack_pop(&sk) ? printf("弹栈成功\n") : printf("弹栈失败\n");printf("此时栈顶元素为%d\n",stack_top(&sk));for (int i = 0; i < 20; i++){stack_pop(&sk) ? printf("弹栈成功\n") : printf("弹栈失败\n");}stack_empty(&sk) ? printf("空\n") : printf("非空\n");return 0;
}

运行结果如下

因为在中间进行了一次出栈，所以在循环中的最后一次弹栈时，栈已经空，进而弹栈失败。

链表栈

链表栈的存储方式是链表，所以在实现栈之前需要先定义链表的基本操作，再实现栈。

下述代码实现了栈的基本操作包括判空、出栈、入栈、访问栈顶，链表栈不存在判满操作，只有数组栈需要，因为链表并不存在满的情况。

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>typedef struct node
{__uint32_t data;struct node *next;
}Node;typedef struct 
{struct node *top;
}stack;
//定义链表的头插法，首元结点就是栈顶，对应了入栈操作
void head_insert(Node *list,__uint32_t data)
{Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = data;new_node->next = list->next;list->next = new_node;
}
//定义链表的头删法，首元结点就是栈顶，对应了出栈操作
void head_delete(Node *list)
{Node *tmp = list->next;list->next = list->next->next;free(tmp);
}
//入栈，调用头插法
bool stack_push(stack *sk,__uint32_t data)
{if(sk->top == NULL)return false;head_insert(sk->top,data);return true;
}
//出栈，调用头删法
bool stack_pop(stack *sk)
{//判断是否为空栈if(sk->top->next == NULL)return false;head_delete(sk->top);return true;
}
//访问栈顶元素
int stack_top(stack *sk)
{//判断是否为空栈if(sk->top->next == NULL)return -1;return sk->top->next->data;
}
//栈判空，也就是链表判空
bool stack_empty(stack *sk)
{return sk->top->next == NULL ? true : false;
}
//摧毁整个链表
void list_destroy(Node *list)
{Node *current = list;while (current){Node *tmp = current;current = current->next;free(tmp);}}int main(int argc, char const *argv[])
{//定义一个链表Node *list = (Node *)malloc(sizeof(Node));list->data = 0;list->next = NULL;//定义栈顶指针stack *sk = (stack *)malloc(sizeof(stack));sk->top = list;stack_empty(sk) ? printf("空\n") : printf("非空\n");for (int i = 0; i < 10; i++){stack_push(sk,i + 1);printf("%d ",stack_top(sk));}printf("\n");printf("栈顶元素为%d\n",stack_top(sk));stack_empty(sk) ? printf("空\n") : printf("非空\n");stack_pop(sk);printf("栈顶元素为%d\n",stack_top(sk));for (int i = 0; i < 10; i++)stack_pop(sk) ? printf("弹栈成功\n") : printf("弹栈失败\n");stack_empty(sk) ? printf("空\n") : printf("非空\n");list_destroy(list);free(sk);return 0;
}

运行结果如下