栈（Stack）基本概念
数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构）
-
定义
栈（Stack）是只允许在一端进行插入或删除操作的线性表
逻辑结构：与普通线性表相同
数据的运算：插入、删除操作有区别
-
重要术语
-
栈顶
允许插入和删除的一端
-
栈底
不允许插入和删除的一端
-
空栈
-
-
基本操作
-
创、销
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
-
-
常考题型
进栈顺序： a → b → c → d → e
有哪些合法的出栈顺序？
-
结论
n个不同元素进栈，出栈元素不同排列的个数为
-
顺序栈的实现
-
用顺序存储方式实现的栈
-
定义
-
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top; //栈顶指针
}SqStack; //Sq:sequence——顺序
void testStack(){
SqStack S; //声明一个顺序栈（分配空间）
//……后续操作……
}顺序存储：给各个数据元素分配连续的存储空间，大小为：MaxSize*sizeof(ElemType)
-
基本操作
-
创（初始化）
-
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top; //栈顶指针
}SqStack; //Sq:sequence——顺序
//初始化栈
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}
void testStack(){
SqStack S; //声明一个顺序栈（分配空间）
//……后续操作……
}
//判断栈空
bool StackEmpty(SqStack S){
if(S.top == -1) //栈空
return true;
else
return false;
}增（进栈）
#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.data[++S.top] = x;
return true;
}删（出栈）
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//出栈操作
bool Pop(SqStack &S,ElemType &x){
if(S.top == MaxSize-1) //栈空，报错
return false;
x = S.data[S.top]; //栈顶元素先出栈
S.top = S.top -1; //指针再减1，数据还残留在内存中，只是逻辑上被删除了
return true;
}查（获取栈顶元素）
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//出栈操作
bool Pop(SqStack &S,ElemType &x){
if(S.top == MaxSize-1) //栈空，报错
return false;
x = S.data[S.top--]
return true;
}
//读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top== -1) //栈空，报错
return false;
x = S.data[S.top]; //x记录栈顶元素
return true;
}另一种方式：
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//初始化栈
void InitStack(SqStack &S){
S.top = 0; //初始化栈顶指针（初始指向0）
}
void testStack(){
SqStack S; //声明一个顺序栈（分配空间）
InitStack(S);
//……后续操作……
}
//判断栈空
bool StackEmpty(SqStack S){
if(S.top ==0) //栈空
return true;
else
return false;
}
//进栈
S.data[S.top++]=x;
//出栈
x=S.data[--S.top];栈满条件：top == MaxSize
缺点：栈的大小不可变
共享栈（两个栈共享同一片空间）
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize] //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}SqStack;
//初始化栈
void InitStack(SqStack &S){
S.top0 = -1; //初始化栈顶指针
S.top1 = MaxSize;
}
满栈的条件：top0 + 1 = top1 总结
链栈的实现
-
用链式存储方式实现的栈
（头插法建立单链表）对头结点的后插操作 → 进栈
（单链表的删除操作）对头结点的后删操作 → 出栈
-
定义
-
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack; //栈类型定义基本操作参考单链表（创：初始化；增：进栈；删：出栈；查：获取栈顶元素）