栈

一、概念

栈是限制在表的一端进行插入和删除操作的线性表，又称为后进先出LIFO或先进后出FILO的线性表。

• 栈顶：允许进行插入、删除操作的一端，又称为表尾
• 栈底：是固定端，又称为表头

二、顺序栈

顺序栈使用一维数组来存储，同时用top指针来指示当前栈顶元素位置

#define MaxSize 100 //栈元素最大个数
typedef struct{
	Elemtype data[MaxSize];
	int top;
} SqStack;

• 栈顶指针：初始设为；
• 栈空：
• 栈满：
• 进栈：栈顶指针加1，再将值送到栈顶元素
• 出栈：先取栈顶元素值，再将栈顶指针减1

TIP

栈和队列的判空、判满条件会根据实际条件不同而变化

共享栈

原理

共享栈是顺序栈地变种，利用栈底位置不变的特性，可以让两个顺序栈共享一个数据空间，将两个栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸。

• 栈顶指针时1号栈为空；栈顶指针时，2号栈为空
• 栈满：仅当两个栈顶指针相邻时
• 1号栈进栈时，先增1再赋值；2号栈进栈时先减1再赋值

优点

能够更有效地利用存储空间，两个栈空间相互调节，只有整个存储空间被栈满时才溢出

三、链栈

采用链式存储的栈称为链栈，是运算受限的单链表，其插入和删除只能在表头位置进行，不存在栈满上溢的情况。

TIP

链栈没有必要像单链表那样附加头结点，栈顶指针top就是链栈的头指针

typedef struct Linknode{
	ElemType data;	//数据域
	struct Linknode *next;	//指针域
} Linknode;