桟
从桟，队列，线性表中理解三者的关系：
从组成元素的逻辑关系来看，栈与队列都属于线性结构。栈和队列与线性表的不同之处在于他们的相关运算具有一些特殊性。更准确地说，一般线性表上的插入，删除运算不受限制，而栈和队列上的插入，删除运算均受某种特殊的限制，因此栈和队列也称为操作受限的线性表。
下面主要介绍基本概念，存储结构，基本运算算法设计和应用实例。
桟是一种常用而且重要的数据结构之一，如用于保存函数调用时所需要的信息，通常在将递归算法换成非递归算法的时候需要使用到桟。
（一）：桟的定义
桟(stack)是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入，删除操作的一端称为栈顶(top),
表的另一端称为桟底(bottom)，当桟中没有数据时称为空桟。桟的插入操作通常称为进桟或入栈(push)，桟的删除操作通常称为出栈或退桟(pop)。
桟的主要特点是"后进先出"(Last In First Out,LIFO)，即后进桟的元素先出桟。每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素，每次出栈的数据元素都是当前栈顶元素。桟也称为后进先出表。
例如，若干个人走进死胡同，假设该死胡同的宽度恰好只能够一个人进出，那么走出死胡同的顺序和走进的顺序正好相反。这个死胡同就是一个桟。
例.用S表示进桟操作，X表示出栈操作，若元素的进桟顺序为1234，为了得到1342的出栈序列，给出相应的S和X操作串。
解：为了得到1342的出栈序列，其操作过程是1进桟，1出栈，2进桟，3进桟，3出栈，4进桟，4出栈，2出栈。所以相应的S和X为SXSSXSXX。
(二):桟的顺序存储结构及其基本运算的实现
桟中数据元素的逻辑关系呈线性关系，所以桟可以像线性表一样采用顺序存储结构进行存储，即分配一块连续的存储空间来存放栈中元素，并用一个变量（如top）指向当前的桟顶元素以后反应栈中元素的变化。采用顺序存储结构的桟称为顺序栈（sequential stack）。
假设桟的元素个数最大不超过正整数MaxSize，所有的元素都具有同一数据类型，即ElemType，也可用下列方式来声明顺序栈的类型 SqStack：
typedef struct
{
ElemType data[MaxSize];//存放桟中的数据类型
int top; //栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack;//顺序栈类型
在顺序桟上对应桟的基本运算算法如下。
1）初始化桟 initStack(&s)
该运算创建一个空桟，由s指向它。实际上就是分配一个顺序桟空间，并将栈顶指针设置为-1。
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc (sizeof(SqStack));//分配一个顺序桟空间，首地址存放在s中
s.top=-1; //栈顶指针为-1；
}
2）.销毁桟DestroyStack(&s)
该运算释放顺序栈s占用的存储空间。算法：
void DestroyStack(SqStack *&s)
{
free(s);
}
3).判断桟是否为空StackEmpty(s)
该运算实际上用于判断条件s.top==-1;是否成立。算法：
bool SackEmpty(SqStack *s)
{
return (s.top==-1);
}
4).进桟push(&s,e)
该运算的执行过程是，在桟不满的条件下先将栈顶指针增1，然后在该位置插入元素e，并返回真；否则返回假。算法：
bool Push(SqStack *&s,ElemType e)
{
if(s.top==MaxSize-1)//桟满的情况，即桟上溢出
return false;
s.top++;//栈顶指针增1
s.data[s.top]=e; //元素e放在桟顶指针出
return true;
}
5).出栈pop(&s, &e)
该运算的执行过程是，在桟不为空的条件下将栈顶元素赋给e，然后将栈顶元素指针减1，并返回真；否则返回假。算法：
bool Pop(SqStack *&s,ElemType &e)
{
if(s.top==-1)//桟为空的情况，即桟下溢出
return false;
e=e.data[s.top]; //取栈顶元素
s.top--;//栈顶指针减1
return true;
}
6）取栈顶元素GetTop(s,&e)
该运算在桟不为空的条件下将栈顶元素赋给e并返回真值；否则返回假值。算法：
bool GetTop(SqStack *s,ElemType &e)
{
if(s.top==-1)
return false;
e=s.data[s.top];
}
