目录
1.栈的定义
2.栈的基本操作
3.栈的顺序存储结构
3.1顺序栈的实现
3.2栈的链式存储结构
1.栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top)。线性表进行插入删除的那一端。
栈底(Bottom)。不允许进行插入和删除的另一端。
空栈。不含任何元素的空表。
2.栈的基本操作
Initstack(&s):初始化一个空栈S。
StackEmpty(S):判断一个栈是否为空，若栈S为空则返回 true，否则返回 false。
Push(&S,x):进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S，&x):出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S,&x):读栈顶元素，但不出栈，若栈s非空，则用x返回栈顶元素。
DestroyStack(&S):销毁栈，并释放栈S占用的存储空间(“&”表示引用调用)。
3.栈的顺序存储结构
栈是一种操作受限的线性表。
3.1顺序栈的实现
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶元素的位置。
栈的顺序存储类型可描述为：
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct {
Elemtype data[MaxSize]; //存放栈中元素
int top; //栈顶指针
} SqStack;
栈顶指针:s.top，初始时设置 s.top=-1;栈顶元素:S.data[s.top]。
进栈操作:栈不满时，栈顶指针先加1，再送值到栈顶。
出栈操作:栈非空时，先取栈顶元素，再将栈顶指针减1。
栈空条件:s.top==-1;栈满条件:S.top=-MaxSize-1;栈长:S.top+1。
另一种常见的方式是:初始设置栈顶指针s.top=0;进栈时先将值送到栈顶，栈顶指针再加1;出栈时，栈顶指针先减1，再取栈顶元素;栈空条件是s.top=-0;栈满条件是S .top==MaxSize。
1）初始化
void InitStack(SqStack &S){
S .top=-1;}
2）判栈空
bool StackEmpty(SqStack S){
if(S .top==-1)
return true;else
return false;}
3）进栈
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1) //栈满，报错
return false;S.data[++S.top]=x;
return true;
}
4)出栈
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1)//栈空，报错
return false;
x=S.data[s.top--];
return true;
}
5)读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top==-1)
return false;x=S.data[S.top]; //x记录栈顶元素
return true;}
3.2栈的链式存储结构
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead 指向栈顶元素
栈的链式存储类型可描述为:
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}LiStack; //栈类型定义
采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。
