栈（Stack）是一种只允许在表的一端（栈顶）进行插入和删除操作的线性表，具有后进先出（LIFO）的特性。其逻辑结构与普通线性表相同。

• 栈顶：允许插入和删除的一端；栈顶元素
• 栈底：不允许插入和删除的一端；栈底元素

n 个不同元素进栈，出栈元素不同排列的个数为：1 n + 1 C 2 n n \frac{1}{n+1} C_{2n}^{n}n+11​C2nn​

顺序栈

顺序栈是利用一组地址连续的存储单元存放栈元素，基于静态数组实现的栈，属于顺序存储。

• 栈底固定在数组下标0位置；
• 用整型变量top作为栈顶指针，标记当前栈顶元素下标(数组下标)；
• 遵循后进先出 LIFO，仅能在栈顶完成插入、删除。
• 所有基本操作时间复杂度都为：O(n)

结构定义 初始化

top的含义：指向栈顶元素所在位置

#include<stdio.h>#include<stdbool.h>// 为了使用 bool 类型#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];// 静态数组存放数据inttop;// 栈顶指针（指向栈顶元素）指向此时栈顶元素，即数组下标}SqStack;// 初始化 创建空栈 top=-1指向栈顶元素所在位置voidInitStack(SqStack&S){S.top=-1;// 关键点：初始时栈中无元素，指针指向 -1// 注意：data 数组里的旧垃圾值不需要清零，因为 top = -1 屏蔽了它们}// 判空boolStackEmpty(SqStack S){returnS.top==-1;// 栈顶指针指向 -1 即为空 返回 true}// 判满boolStackFull(SqStack S){returnS.top==MaxSize-1;// 数组下标 最大：MaxSize -1}

进栈

// 进栈 ：在栈顶插入元素 eboolPush(SqStack&S,inte){// 1. 先判断是否已满if(S.top==MaxSize-1)returnfalse;// 2. top 先加 1（指向新的空位），再把元素放进去S.top=S.top+1;// 即 S.top++;S.data[S.top]=e;// 或者合并为一行：S.data[++S.top] = e;returntrue;}

出栈

出栈，数据还残留在内存当中，只是逻辑上被删除了（被top屏蔽了）。

// 出栈：删除栈顶元素，并带回其值boolPop(SqStack&S,int&e){// 1. 先判断是否为空if(S.top==-1)returnfalse;// 2. 先取出当前栈顶元素，再让 top 减 1e=S.data[S.top];S.top=S.top-1;// 即 S.top--;// 或者合并为一行：e = S.data[S.top--];returntrue;}// 物理上还在，但逻辑上被 top 指针屏蔽了。下次入栈新元素时，会直接覆盖这个位置。

查找 （取栈顶）

// 取栈顶：只读操作，不删除元素，所以不使用 &SboolGetTop(SqStack S,int&e){if(S.top==-1)returnfalse;e=S.data[S.top];// top 不动returntrue;}

取栈顶对比出栈操作：

销毁

顺序栈的清空：S.top = -1;即可。因为数组空间是静态分配的，逻辑上清空指针即可，物理内存不需要free（除非用了动态malloc）。回收：函数运行结束后系统自动回收内存(因为是静态数组)。

另一种方式 （top含义）

top的含义：指向栈顶元素的下一个位置（即待插入位置）

#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];inttop;}SqStack;// 初始化创建空栈voidInitStack(SqStack&S){S.top=0;// 初始指向 0：指向下一个可插入元素的位置}// 判空boolStackEmpty(SqStack S){returnS.top==0;// 栈顶指针指向 0 即为空栈 返回 true}// 判满 顺序栈的缺点：站的大小不可变boolStackFull(SqStack S){returnS.top==MaxSize;}// 进栈S.data[S.top]=e;S.top=S.top+1;// S.top++;// 上面两行等价于： S.data[S.top++] = x;// 出栈S.top=S.top-1;// S.top--;e=S.data[S.top];// 上面两行等价于： x = S.data[--S.top];

共享栈

两个栈共享同一段数组空间data[0 ... MaxSize-1]，两个栈从两边往中间增长，极大提高内存利用率。

#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];inttop0;// 0 号栈 栈顶指针inttop1;// 1 号栈 栈顶指针}SqStack;voidInitStack(ShStack&S){S.top0=-1;// 初始化栈顶指针S.top1=MaxSize;}// 栈满条件：top0 + 1 = top1;// 两个栈顶指针相邻，代表数组被完全占满，无空位

图示：

[ 栈0元素 | 栈0元素 | 空闲 | 栈1元素 | 栈1元素 ] ↑ top0 ↑ top1

总结

维度	top=-1 （推荐）	top=0
top 的含义	指向栈顶元素所在位置	指向栈顶元素的下一个位置（即待插入位置）
初始值	top = -1	top = 0
栈空条件	top == -1	top == 0
栈满条件	top == MaxSize - 1	top == MaxSize
入栈动作（Push）	data[++top] = e;（先移指针，再放元素）	data[top++] = e;（先放元素，再移指针）
出栈动作（Pop）	e = data[top- -];（先取元素，再移指针）	e = data[- - top];（先移指针，再取元素）
记忆口诀	“顶指元素，先移后放”	“顶指空位，先放后移”