1.栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表（LIFO结构）。
插入元素的操作叫做入栈，删除栈顶元素的操作叫做出栈。
栈的抽象数据类型的定义：
ADT Stack {
数据对象：D＝{ai| ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ | ,ai-1,ai∈D, i=2,...,n }
约定an端为栈顶，a1端为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈 S。
DestroyStack(&S)
初始条件：栈 S 已存在。
操作结果：栈 S 被销毁。
ClearStack(&S)
初始条件：栈 S 已存在。
操作结果：将 S 清为空栈。
StackEmpty(S)
初始条件：栈 S 已存在。
操作结果：若栈 S 为空栈，则返回TRUE，否则返回FALSE。
判定栈是否为空栈是栈在应用程序中经常使用的操作，通常以它作为循环结束的条件。
StackLength(S)
初始条件：栈 S 已存在。
操作结果：返回栈 S 中元素个数，即栈的长度。
GetTop(S, &e)
初始条件：栈 S 已存在且非空。
操作结果：用 e 返回S的栈顶元素。
这是取栈顶元素的操作，只以 e 返回栈顶元素，并不将它从栈中删除。
Push(&S, e)
初始条件：栈 S 已存在。
操作结果：插入元素 e 为新的栈顶元素。
Pop(&S, &e)
初始条件：栈 S 已存在且非空。
操作结果：删除 S 的栈顶元素，并用 e 返回其值。
StackTraverse(S, visit( ))
初始条件：栈 S 已存在且非空，visit( )为元素的访问函数。
操作结果：从栈底到栈顶依次对S的每个元素调用函数visit( )，
一旦visit( )失败，则操作失败。
}
栈有两种存储方法：顺序栈和链式栈。下面介绍顺序栈。链式栈可参考链表结构。
2.栈的操作
栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
一般情况下，先为栈分配一个基本容量，然后在使用过程中，当栈的空间不够用时再逐段扩大。：
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
其中，stacksize表示栈的最大容量。base称为栈底指针，top为栈顶指针。
顺序栈的存储表示与实现：
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S);
Status DestoryStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack &S);
int StackLength(SqStack &S);
Status GetTop(SqStack &S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackTraverse(SqStack S,Status(*visit()));
//函数算法功能描述
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));//(好难理解)
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return ok;
}
Status GetTop(SqStack &S,SElemType &e){
if(S.top==S.base) return ERROR;
e=*(S.top-1);
}
Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){//栈满追加空间
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return ok;
}
Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return ok;
}
//等等.
