一、栈
1.
栈(stack)：是限定仅在表尾进行插入和删除操作的线性表。其中，允许插入和删除的一端被称为栈顶(top)，另一端被称为栈底(bottom)，不含任何数据元素的栈被称为空栈。栈又被称为后进先出(Last In First Out)的线性表，简称LIFO结构。 栈的插入操作为进栈，栈的删除操作为出栈。
2.栈的抽象数据类型 ADT 栈(stack) Data 同线性表。元素具有相同类型，相邻元素具有前驱和后继关系。 Operation InitStack(*S)：初始化操作，建立一个空栈S。 DestoryStack(*S)：若栈存在，则销毁它。 ClearStack(*S)：将栈清空。 StackEmpty(S)：若栈为空，返回true，否则返回false。 GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素。 Push(*S,e)：若栈S存在，插入新元素e到栈S中并称为栈顶元素 Pop(*S,*e)：删除栈S中栈顶元素，并用e返回其值 StackLength(S)：返回栈S的元素个数 endADT
二、栈的存储结构
1.栈的顺序存储结构及实现(复杂度均为O(1))
(1)栈顺序结构定义 #define OK 1 #define ERROR 0 typedef int SElemType; //SElemType类型根据实际情况而定，这里假设为int typedef struct { SElemType data[MAXSIZE]; //栈存储空间大小MAXSIZE int top; //用于栈顶指针 }SqStack;
(2)进栈操作(从栈顶插入一个元素) 算法思路： a.判定是否栈满; b.栈顶加1; c.将元素插入到 实现：插入元素e为新的栈顶元素
Status Push(SqStack *S,SElemType e)
{
if(S->top==MAXSIZE-1) //栈顶=MAXSIZE-1，即数组的最后一个存储位置，说明栈满
{
return ERROR;
}
S->top++; //栈顶加1
S->data[S->top]=e; //将元素入栈
return OK;
}
(3)出栈操作(从栈顶删除一个元素) 算法思路： a.判定栈是否为空; b.将栈顶元素保存到指针变量e所指向的存储位置中; c.栈顶减1. 实现：若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==-1) //空栈
{
return ERROR;
}
*e=S->data[S->top];
S->top--;
return OK;
}
(4)两栈共享空间 栈的顺序存储只准栈顶进出元素，所以不存在线性表插入和删除时需要移动大量的元素，但是有个缺陷是必须事先确定数组存储空间大小。当两个栈数据类型一样是，我们可以将两个栈所开辟的空间共享使用。
A.思想：将栈1的栈底，即为共享空间的栈底(下标为0);另一个栈的栈底为共享栈的末端(下标为数组长度n-1处)，其中top1和top2是栈1和栈2的栈顶指针。对于共享栈，若栈2是空栈(top2=n)，栈1的tZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcDE9bi0xLMu1w/fVuzHC+sHLo7vI9NW7McrHv9XVuyh0b3A9LTEpLNW7MrXEdG9wMj0wo6zLtcP31bsywvrBy6GjvLS5ss/t1bvC+sz1vP6junRvcDEmIzQzOzE9PXRvcDKhowpCLrmyz+3Vu7/VvOS94bm5CnR5cGVkZWYgc3RydWN0CnsKICAgIFNFbGVtVHlwZSBkYXRhW01BWFNJWkVdOyAgICAvL7ao0uXSu7j2yv3X6bTmtKK/1bzko6y089ChzqpNQVhTSVpFvLTOqtW7tPPQoQogICAgaW50IHRvcDE7ICAgIC8v1bsx1bu2pda41esKICAgIGludCB0b3AyOyAgICAvL9W7MtW7tqXWuNXrCn1TcURvdWJsZVN0YWNrOwpDLrmyz+3Vu9Sqy9jI69W7stnX9wrL47eoy7zCt6O6CmEuytfPyMXQts+5ss/t1bvKx7fx1bvC+jsKYi7NqLn9c3RhY2tOdW1iZXKyzsr9xdC2z7LlyOvExLj21bsKICAgIMj0zqrVuzGjrNTy1bu2pXRvcDHU9jGjrNTZvavUqsvYZcjr1bs7yPTOqtW7MqOs1PLVu7aldG9wMrz1MaOs1Nq9q9Sqy9hlyOvVu6GjCsq1z9ajurLlyOvUqsvYZc6q0MK1xNW7tqXUqsvYCjxwcmUgY2xhc3M9"brush:sql;">Status Push(SqDoubleStack *S,SElemType e,int stackNumber) { if(S->top1+1==S->top2) //判定共享栈是否栈满(top1+1=top2) { return ERROR; } if(stackNumber==1) //栈1有元素进栈,栈顶top1加1 S->data[++S->top1]=e; else if(stackNumber==2) S->data[--S->top2]=e; //栈2有元素进栈，栈顶top2减1 return OK; } D.共享栈元素出栈操作 算法思想： a.判断哪一个栈; b.若为栈1，则先将元素赋值给指针变量e指向的空间位置，再栈顶top1减1; 若为栈2，则先将元素赋值给指针变量e指向的空间位置，再栈顶top2增1; 实现：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if(stackNumber==1) //若删除元素属于栈1
{
if(S->top1==-1) //空栈
return ERROR;
*e=S->data[S->top1--]; //将元素赋值给e，栈顶再减1
}
else if(stackNumber==2)//若删除元素属于栈1
{
if(S->top2==MAXSIZE) //空栈
return ERROR;
*e=S->data[S->top2++]; //将元素赋值给e，栈顶再减1
}
return OK;
}
升华笔记1： 1.栈的顺序存储结构是通过数组来实现的，下标为0为栈底，因为首元素都哦存在栈底变化最小。当栈存在一个元素时，栈顶top为0，如果为空栈则top=-1,这也是判断栈是否为空栈的条件。另外，要区别存储栈的长度StackSize(MAXSIZE)和存储位置。 2.两栈共享空间只适用于元素数据类型相同的两个栈，且入栈是先修改栈顶再元素入栈;出栈是先元素出栈再修改栈顶。
2.栈的链式存储结构及实现
(1)链栈的结构 //链结点:包含数据域和指针域 typedef struct StackNode { SElemType data; //数据域 str