Stack类型定义
栈是限定仅在表尾进行插入和删除操作的线性表，又称为后进先出(last in first out)的线性表(LIFO结构)，表尾称为栈顶，表头称为栈底，不含元素则称为空栈；
抽象数据类型:
InitStack(&S) //构造空栈SDestoryStack(&S) //销毁栈SClearStack(&S) //将S清为空栈StackEmpty(S) //若S为空栈返回TRUE,否则FALSEStackLength(S) //返回栈S的元素个数，即栈的长度GetTop(S, &e) //用e返回S的栈顶元素Push(&S, e) //插入元素e为新的栈顶元素Pop(&S, &e) //删除S的栈顶元素，并用e返回其值StackTraverse(S, visit()) //从栈顶到栈底依次对S的每个元素调用visit(),visit()失败则操作失败顺序存储结构存储表示
其中base为NULL时表示栈结构不存在，top==base可作为栈空的标记;
#define STACK_INIF_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define OK 1#define ERROR 0typedef int SElemType;typedef int Status;typedef struct{ SElemType *base; //栈不存在为NULL SElemType *top; int stacksize;}SqStack;基本实现InitStack
Status InitStack(SqStack *S){ // 构造空栈S S->base = (SElemType *)malloc(STACK_INIF_SIZE * sizeof(SElemType)); if (!S->base) return ERROR; S->top = S->base; S->stacksize = STACK_INIF_SIZE; return OK;}GetTop
Status GetTop(SqStack S, SElemType *e){ // 若栈不空，用e返回S的栈顶元素 if (S.top == S.base) return ERROR; (*e) = *(S.top - 1); return OK;}Push
Status Push(SqStack *S, SElemType e){ // 插入元素e为栈顶元素 if (S->top - S->base >= S->stacksize) { // 栈满，追加储存空间 S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S->base) return ERROR; S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } *S->top++ = e; return OK;}Pop
Status Pop(SqStack *S, SElemType *e){ // 若栈不空，则删除S的栈顶元素，并用e返回其值 if (S->top == S->base) return ERROR; (*e) = *--S->top; return OK;}测试
int main(){ SqStack *S = (SqStack *)malloc(sizeof(SqStack)); InitStack(S); Push(S, 1); printf("%d %d\n", *S->base, *(S->top - 1)); Push(S, 2); printf("%d %d\n", *S->base, *(S->top - 1)); int *e = (int *)malloc(sizeof(int)); Pop(S, e); printf("%d %d\n", *S->base, *(S->top - 1)); printf("%d", *e); return 0;}链式存储结构存储表示
链式存储便于多个栈共享存储空间以及提高其效率，且不存在栈满的情况，通常采用单链表实现，并规定所有操作都是在表头进行；这里没有头结点，直接指向栈顶元素，对于空栈即top == base = NULL；
//节点typedef struct StackNode{ ElemType data; struct StackNode *next;}StackNode, *LinkStackPrt;//链栈typedef struct LinkStack{ LinkStackPrt top; int count;}LinkStack;基本实现Push
Status Push(LinkStack *S, ElemType e){ //插入新栈顶元素e //创建新节点 LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode)); p->data = e; p->next = S->top; S->top = p; S->count++; return OK;}Pop
Status Pop(LinkStack *S, ElemType *e){ LinkStackPrt P; if(StackEmpty(*S)) return ERROR; *e = S->top->data; p = S->top; S->top = S->top->next; free(p); S->count--; return OK;}栈的应用表达式求值波兰式（前缀表达式）
从左向右读入表达式，如果一个操作符后面跟着两个操作数时，将计算结果作为操作数替换这个操作符和两个操作数，直至计算完成；
such as 2 + 3 * (5 – 1)，其波兰式为 + 2 * 3 – 5 1；
逆波兰式（后缀表达式）
相较于波兰式，逆波兰式要更为直接，当遇到操作符时，将前面两个操作数与这个操作符进行计算，结果替换；
如上的 2 + 3 * (5 – 1)用逆波兰式表示为 2 3 5 1 – * +;
这个过程很容易用栈来实现，将2, 3, 5, 1依次压入栈中，当压入 – 时，判定为操作符，Pop 5, 1,计算结果后再压入栈中，直至压入完成，栈中元素即运算结果；
中缀表达式转化为逆波兰式
由于计算机中广泛应用后缀表达式，因此中缀表达式转为后缀表达式很有必要；
从左向右遍历，遇到数字，输出到逆波兰式中；遇到符号，判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出到逆波兰式中，并将当符号进栈，直至输出结束
如 2 + 3 * (5 – 1)则过程如下：
- 2，输出到表达式中，2，栈为空；
- +，到栈中，2，+；
- 3，输出到表达式中，2 3，+；
- *，到栈中，2 3，+ *；
- （，到栈中，2 3，+ * （；
- 5，表达式，2 3 5，+ * （；
- -，栈中，2 3 5，+ * （ -；
- 1，表达式，2 3 5 1，+ * （ -；
- ），栈顶元素依次出栈并输出到表达式中，即2 3 5 1 – * +；
行编辑程序
在栈的功能下，实现用户在终端输入出现差错时，及时更正；
栈与递归的实现
……