堆栈简称栈
堆栈是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由一个称为栈顶指针的变量给出。当表中没有元素时，称之为空栈。
由于堆栈只允许在一端操作，后进入的数据往往会先处理，简称为后进先出，如下图
1、插入（进栈、入栈）
2、删除（出栈、退栈）
3、测试堆栈是否为空
4、测试堆栈是否已满
5、检索当前栈顶元素
其操作收到位置的限制，所以只是一般线性表操作的一个子集。
1、构造原理
描述堆栈的顺序存储结构最简单的方法是利用一维数组STACK[ 0: M–1 ]来表示，同时定义一个整型变量(不妨取名为top)给出栈顶元素的位置，如下图
top等于堆栈顶部的下标
堆栈的溢出：
上溢：当堆栈已经满时做插入操作（top=M-1）
下溢：当堆栈为空时做删除操作（top=-1）
堆栈类型定义如下：
#define M 1000SElemType STACK[M];int top; //初始时 top=-12、初始化堆栈
void INITIALS( int &top ){ top= –1;}3、测试堆栈是否为空
int EMPTYS( int top ){ return top == –1; //栈空返回 1 ，否则返回 0}4、测试堆栈是否已满
int FULLS( int top ){ return top==M–1; //栈满返回 1 ，否则返回 0}5、插入（进栈）算法
int PUSH( SElemType STACK[ ], int &top, SElmeType item ){ if( FULLS(top) ) return 0; else { STACK[++top]=item； return 1; }}6、删除（出栈）算法
int POP( SElemType STACK[ ], int &top, SElemType &item ){ if( EMPTYS(top) ) return 0; else{ item=STACK[top--]; //先取出top，再top减1 return 1; }} 多栈共享连续空间问题在堆栈的顺序存储方式中，有时为了减少空间碎片，提高空间利用率，会设置多个堆栈共享一个连续空间，以下以两个堆栈共享一个数组为例，如下：
入栈的C语言实现（一）如下：
int PUSH( SElemType STACK[ ], int top[ ], int i, SelemType item ){ if(top[0]==top[1]–1) /* 栈满 */ return 0; else{ if(i==1) /* 插入第1个栈 */ STACK[++top[0]]=item; else /* 插入第2个栈 */ STACK[– –top[1]]=item; return 1; }}入栈的C语言实现（二）如下：
int PUSH( SElemType STACK[ ], int top[ ], int i, SElemType item ){ if (top[0]==top[1]–1) return 0; else { if (i==1) top[0]++; /* 修改第1个栈顶指针 */ else top[1]– –; /* 修改第2个栈顶指针 */ STACK[top[i–1]]=item; return 1; }}一和二本质一样，只不过二的写法更简洁；
出栈的C语言实现如下：
1、构造原理
链接堆栈就是用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量( 这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。栈为空时，有top=NULL。如下图
C语言实现如下：
typedef struct node { SElmeType data; struct node *link;} STNode, *STLink;2、堆栈初始化
void INITIAL( STLink &top ){ top = NULL;}3、测试堆栈是否为空
int EMPTYS( STLink top ){ return top==NULL;}4、插入（进栈）算法 （不必判断栈满）
int PUSHLINK( STLink &top, SElemType item ){ STLink p; if( !(p=(STLink)malloc(sizeof(STNode)) ) //申请一个新的链节点 return 0; else{ p->data=item; /*将item送新结点数据域*/ p->link=top; /*将新结点插在链表最前面*/ top=p; /*修改栈顶指针的指向*/ return 1; }}5、删除（退栈）算法
int POPLINK( STLink &top, SElemType &item ){ STLink p; if ( EMPTYS(top) ) return 0; /* 删除失败*/ else { p=top; /* 暂时保存栈顶结点的地址*/ item=top->data; /*保存被删栈顶的数据信息*/ top=top->link; /* 删除栈顶结点*/ free(p); /* 释放被删除结点*/ return 1; /* 删除成功*/ }} 堆栈的应用1、符号匹配检查
2、数制转换
3、递归
4、表达式计算
5、迷宫