脚踏实地《数据结构第三章栈和队列》第一节：栈

本节常考题型栈问题一：有那些合法的出栈顺序?总数
进栈和出栈交替进行的话，就有上图中这么多的出栈顺序
一：栈的基础概念
1.1 栈（Stack）的基本概念（定义）栈( Stack）：是只允许在一端进行插入或删除操作的线性表

生活中：烤串、叠碗等

一些术语：如图所示

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

特点：后进先出
1.2 栈的基本操作 InitStack(&S)：初始化栈。构造一个空栈S ，分配内存空间。创
DestroyStack(&L):销毁栈。销毁并释放栈S所占用的内存空间。销
Push(&S,x):进栈，若栈s未满，则将x加入使之成为新栈顶。增
Pop(&S,&x):出栈，若栈s非空，则弹出栈顶元素，并用x返回。删

删除栈顶元素

GetTop(S,&x):读栈顶元素。若栈s非空，则用x返回栈顶元素。查

不删除栈顶元素
栈的使用场景中大多只访问栈顶元素

常用操作：
StackEmpty(S):判断一个栈S是否为空。若S为空，则返回true ，否则返回false 。
1.3 知识回顾与重要考点二：顺序栈（栈的顺序存储结构实现）
2.1 顺序栈的定义

#define MaxSize 10 //定义栈中元素的最大个数typedef struct{	ElemType data[MaxSize];//静态数组放栈中元素	int top;//栈顶指针} SqStack;

top是指向栈顶的元素位置，如上图所示
void testStack(){ SqStack S;//声明一个顺序栈(分配空间) // 。。。后续操作。。。} 2.2 初始化操作

#define MaxSize 10 //定义栈中元素的最大个数typedef struct{	ElemType data[MaxSize];//静态数组放栈中元素	int top;//栈顶指针} SqStack;//初始化栈void InitStack(SqlStack &S){	S.top = -1; //初始化栈顶指针}void testStack(){	SqStack S;//声明一个顺序栈(分配空间)	InitStack(S);	// 。。。后续操作。。。}

2.3 判断栈空 //判断栈空bool StackEmpty(SqStack S){ if(S.top == -1)//栈空return true; else//不空return false;} 2.4 进栈操作（增）

#define MaxSize 10 //定义栈中元素的最大个数typedef struct{	ElemType data[MaxSize];//静态数组放栈中元素	int top;//栈顶指针} SqStack;//新元素进栈bool Push(SqStack &S,ElemType x){	if(S.top == MaxSize-1)//栈满,报错return false;	S.top = S.top + 1;//指针先加1	S.data[S.top] = x;//新元素入栈	return true;}

2.5 出栈操作（删）

#define MaxSize 10 //定义栈中元素的最大个数typedef struct{	ElemType data[MaxSize];//静态数组放栈中元素	int top;//栈顶指针} SqStack;//出栈操作bool Pop(SqStack &S,ElemType $x){	if(S.top == -1)	//栈空 ， 报错return false;	x=S.data[S.top];//栈顶元素先出栈	S.top = S.top - 1;//指针再减1	return true;}

2.6 读取栈顶元素操作（查）

#define MaxSize 10 //定义栈中元素的最大个数typedef struct{	ElemType data[MaxSize];//静态数组放栈中元素	int top;//栈顶指针} SqStack;//读取栈顶操作bool Pop(SqStack &S,ElemType &x){	if(S.top == -1)//栈空 ， 报错return false;	x=S.data[S.top];//x记录栈顶元素	return true;}

2.7 上面操作另一种实现方式（注意）
如果想要将一个新的元素入栈的话，与之前的方式刚好相反
2.8 共享栈顺序栈是使用静态数组零存放数据元素，因此静态数组的数据存满之后，其容量是不可以改变的，
解决上面的问题方法：

链式存储方式实现栈
在刚开始的时候给这个栈分配一个比较大片的连续存储空间（导致内存空间的浪费）
使用共享栈的方式提高第二种方式的空间利用率

【脚踏实地《数据结构第三章栈和队列》第一节：栈】共享栈：两个栈共享一片空间
代码实现：

# define MaxSize 10//定义栈中元素的最大个数typedrf struct{	ElemType data[MaxSize];//静态数组存放栈中元素	int top0;//0号栈栈顶指针	int top1;//1号栈战顶指针} ShStack;//初始化栈void InitStack(ShStack &S){	S.top0 = -1;//初始化栈顶指针	S.top1 = MaxSize;}

以后如果从0号栈存放指针的话，就是从下往上依次递增的，
如果要往1号栈放入数据元素的话，这个栈的栈顶就是从上往下依次递增的
如此在逻辑上实现了两个栈，但是在无论上又是共享同一片的存储空间，提高了空间利用率
栈满的条件: top0+ 1 == top1
2.9 知识回顾与重要考点
在路逻辑上清空一个栈，其实只需要将top指针指向初始化的那个位置就可以了
在本节中，我们是通过变量声明的方式分配内存空间，并没有使用malloc函数，所以给栈分配的内存空间会在函数运行结束后系统自动回收内存
三：链栈（栈的链式存储方式实现）
3.1 用链式存储方式实现的栈用链式存储方式实现的栈，其本质上也是一个单链表，只不过我们想要规定只能在单链表的链头一端进行插入和删除操作（链头=栈顶）
3.1.1 链栈的定义 typedef struct Linknode{ ElemType data;//数据域 struct Linknode *next;//指针域}*LiStack;//栈类型定义 3.2 其他剩下的操作与之前链表的操作类似，我在这里也偷懒了，不说了