数据结构之栈和队列（一）
本文主要介绍2种操作受限的线性表结构：栈（Stack）和队列（Queue），包括它们的概念和存储结构。 除此之外，还会简单介绍一下特殊矩阵的压缩存储。
栈（Stack）
栈是只允许在一端进行插入或删除操作的线性表。它满足后进先出（LIFO）。
栈的基本操作：
InitStack(&S)：初始化StackEmpty(S)：判断栈是否为空Push(&S,x)：进栈，若栈S未满，将x加入使之成为新的栈顶Pop(&S,x)：出栈，若栈S非空，弹出栈顶元素，并用x返回GetTop(S,&x)：读栈顶元素，若栈S非空，用x返回栈顶元素ClearStack(&S)：销毁栈，释放S存储空间
栈的顺序存储
栈的顺序存储也称顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设有一个**指针（top）**指示当前栈顶的位置。
栈的顺序存储类型描述如下：
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
栈顶指针（top）初始值不同，进栈出栈操作也有所不同，栈顶指针初始值一般取-1或0，对应操作如下：
初始化栈
void InitStack(&S){
s.top==-1; //初始化栈顶指针
}
判栈空
bool StackEmpty(S){
if(s.top==-1)
return true; //栈空
else
return false;
}
进栈
bool Push(SqStack &S,ElemType x){
if(s.top==MaxSize-1) //栈满报错
return false;
S.data[++S.top]=x; //指针先加1，再进栈
return true;
}
出栈
bool Pop(SqStack &S,ElemType x){
if(s.top==-1) //栈空报错
return false;
x=S.data[S.top--]; //先出栈，指针再减1
return true;
}
读取栈顶元素
bool GetTop(SqStack &S,ElemType &x){
if(S.top==-1) //栈空报错
return false;
x=S.data[S.top]; //x记录栈顶元素
return true;
}
栈的链式存储
链式存储的栈又称链栈，优点是便于多个栈共享存储空间，提高效率，并且不存在栈满上溢情况。
- 常采用单链表实现，规定操作都是在单链表的表头进行
- 一般规定链栈没有头结点，Lhead指向栈顶元素
栈的链式存储类型描述如下：
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack;
共享栈
共享栈是为了高效的利用存储空间。利用栈底的位置相对不变这一特性，我们可以让2个顺序栈共享一个一维数据空间。这2个栈的栈底分别设在共享空间的两端，两个栈顶向共享空间延伸。
2个栈的进出栈操作如下图所示：
