目录
一、栈的基本概念
（一）栈的定义
????????只允许在 一端进行插入或删除操作的线性表
- 栈顶：允许进行插入删除的一端
- 栈底：固定的，不允许插入和删除的另一端
- 空栈：不含任何元素的空表
? ? ? ? 栈的一个数学性质，n个不同元素进栈，出栈元素不同排序的个数为
（二）栈的基本操作
| 基本操作 | 操作函数 | 备注 |
| 初始化 | InitStack(&L) | 初始化一个空栈 |
| 判空 | StackEmpty(S) | 若栈空返回true，否则返回false |
| 进栈 | Push（&S,x） | 进栈，若栈S未满，则将x加入成为栈顶 |
| 出栈 | Pop（&S） | 出栈，若栈S非空，则弹出栈顶元素，并用x返回 |
| 读栈顶元素 | GetTop（S,&x） | 读栈顶元素，若栈S不为空，则用x返回栈顶元素 |
| 销毁栈 | DestroyStack（&S） | 销毁栈，并释放S占用的存储空间 |
二、栈的顺序存储结构
（一）顺序栈的实现
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;????????栈顶指针：S.top,也就是栈顶在数组中的位置，一般初始的时候设置为-1
? ? ? ? 栈顶元素：S.data[S.top]
? ? ? ? 栈空条件：S.top == -1，栈满条件：S.top = =MaxSize -1
? ? ? ? 还有一种情况是S.top初始化为0的情况，这种情况表示S.top指向栈顶元素的下一个位置?
（二）顺序栈的基本运算
1.初始化
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;
void InitStack(SqStack &S)
{
S.top=-1; //初始化栈顶指针
}
int main(){
SqStack S; //声明一个顺序栈
InitStack(S); //初始化顺序栈
return 0;
}
2.判栈空
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;
bool StackEmpty(SqStack &S)
{
if(S.top == -1)
return true; //栈空
else
return false; //栈不为空
}
int main(){
SqStack S; //声明一个顺序栈
InitStack(S); //初始化顺序栈
if(StackEmpty(S)) //判空
print("hello");
return 0;
}
3.进栈
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;
bool PushStack(SqStack &S,ElemType x)
{
if(S.top == MaxSize-1)
return false; //栈满报错
else
{
S.data[++S.top] = x; //指针先+1，再进栈
return true;
}
}
int main(){
SqStack S; //声明一个顺序栈
ElemType x;
InitStack(S); //初始化顺序栈
PushStack(S,x); //进栈操作
return 0;
}
4.出栈
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;
bool PopStack(SqStack &S,ElemType x)
{
if(S.top == -1)
return false; //栈空报错
else
{
x = S.data[S.top--] //先出栈，再指针-1
return true;
}
}
int main(){
SqStack S; //声明一个顺序栈
ElemType x;
InitStack(S); //初始化顺序栈
PopStack(S,x); //出栈操作
return 0;
}
5.读栈顶元素
#define MaxSize 50
typedef sturct
{
ElemType data[MaxSize]; //存放在栈中的元素
int top; //栈顶指针在数组中的相对位置
}SqStack;
bool GetTop(SqStack &S,ElemType x)
{
if(S.top == -1)
return false; //栈空报错
else
{
x = S.data[S.top] //记录栈顶元素
return true;
}
}
int main(){
SqStack S; //声明一个顺序栈
ElemType x;
InitStack(S); //初始化顺序栈
GetTop(S,x); //读栈顶元素
return 0;
}
（三）共享栈
?? ? ? ? 两个顺序栈共享一个一维数组，将两个栈的栈底分别设置在共享空间的两端，栈顶向共享空间中间延伸
? ? ? ??进栈时先动指针再赋值，出栈时先取值再动指针
三、栈的链式存储结构
（一）链栈的实现
? ? ? ? 采用链式存储的栈称为链栈，优点是不存在栈满上溢的情况
? ? ? ? 通常用单链表实现，并规定所有操作都是在单链表的表头进行的，这里规定链栈没有头结点，Lhead指向栈顶元素
? ? ? ? ?栈的链式存储类型代码如下
typedef struct Linknode
{
ElemType data;
struct Linknode *next;
}*Listack,Linknode;?（二）链栈的基本操作
? ? ? ? ?目前参照线性表的链式存储之后再继续完善
四、经典例题
（一）选择题
1.栈和队列具有相同的（）
????????A.抽象数据类型? ? ? ? ? ? ? ? B.逻辑结构? ? ? ? ? ? ? ? C.存储结构? ? ? ? ? ? ? ? D.运算
? ? ? ? 栈和队列同属于线性结构，也就是同一个逻辑结构
? ? ? ? 该知识点来自于（可点击查看）→数据结构绪论
2.设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（）
??A.只有表头节点指针，没有表尾结点指针?的双向循环链表
? B.只有表尾结点指针，没有表头指针的双向循环链表
? C.只有表头节点指针，没有表尾指针的单向循环链表
? D.只有表尾结点指针，没有表头指针的单向循环链表
? ? ? ? 循环链表，在有删除操作的情况下，都需要考虑一点，找删除节点的前驱节点并修改其指针。在表头进行删除操作，表尾结点是前驱节点，单向循环链表无法一步找到表尾结点，因此选C
3.采用共享栈的好处是（）
? A.减少存取时间，降低发送上溢的可能
? B.节省存储空间，降低发生上溢的可能
? C.减少存取时间，降低发生下溢的可能
? D.节省存储空间，降低发生下溢的可能
? ? ? ? 节省存储空间这个不用说，栈只可能发生上溢，所以选B
