堆栈的基本概念
堆栈是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是：线性表允许在任意位置插入和删除数据元素操作，而堆栈只允许在固定一端进行插入和删除数据元素操作
根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入堆栈的数据元素总是最先退出堆栈，因此，堆栈也称作后进先出的线性表，或简称后进先出表。
例子
设有数据元素序列A,B,C，是否可以利用一个堆栈，得到数据元素序列B, A, C。
分析：按照如下方法操作：A入栈，B入栈，B出栈，A出栈，C入栈，C出栈，则输出数据元素序列为B, A, C。因此，利用一个堆栈，可以把数据元素序列A, B, C变换为数据元素序列B, A,C。其操作过程的堆栈内容示意图下图所示。
输出序列为B, A, C的操作过程
在软件设计中，需要利用堆栈进行数据元素序列转换的例子很多。例如，在编译软件系统中，就需要频繁地把中缀表达式形式的算术表达式，转换成后缀表达式形式的算术表达式。又如，任何支持递归算法的程序设计语言，都是借助堆栈来实现递归算法需要的后调用的过程先执行的要求的。
堆栈操作集合
初始化StackInitiate(S)：初始化堆栈S。
非空否StackNotEmpty(S)：堆栈S非空否。若堆栈非空，则函数返回1；否则函数返回0。
入栈StackPush(S, x)：在堆栈S的当前栈顶插入数据元素x。
出栈StackPop(S, d)：把堆栈S的当前栈顶数据元素删除并由参数d带回。若出栈成功，则返回1；失败，则返回0。
取栈顶数据元素StackTop(S, d)：取堆栈S的当前栈顶数据元素并由参数d带回。若取到数据元素，则返回1；否则返回0。
顺序堆栈的存储结构
顺序存储结构的堆栈称作顺序堆栈。
顺序堆栈和顺序表的数据成员是相同的，不同之处是，顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。
顺序堆栈的存储结构示意图如图3-3所示。其中，a0, a1, a2, a3, a4表示顺序堆栈要存储的数据元素序列，stack表示顺序堆栈存放数据元素的数组，MaxStackSize表示顺序堆栈数组stack的最大存储单元个数，top表示顺序堆栈数组stack的当前栈顶位置。
顺序堆栈的存储结构示意图
定义结构体SeqStack如下：
#define MaxSize 50 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; //连续内存空间存放栈中元素 int top; //存放栈顶元素在data数组中的下标 }SqStack;
顺序堆栈的操作实现
初始化StaticInitiate(*S) void StaticInitiate(*S) { S->top=0; //初始化栈顶下标值 }
非空否StackNotEmpty(S)
int StackPush(SeqStack *S,DataType x)//把数据元素x存入顺序堆栈S中，入栈成功返回1，否则返回0 { if(S->top>=MaxStackSize) { printf("堆栈已满，无法插入！\n") return 0; } else { S->Stack[S->top]=x; S->top++; return 1; } }
入栈StackPush(SeqStack *S,DataType x)
int StackPush(SeqStack *S,DataType x)//把数据元素x存入顺序堆栈S中，入栈成功返回1，否则返回0 { if(S->top>=MaxStackSize) { printf("堆栈已满，无法插入！\n") return 0; } else { S->Stack[S->top]=x; S->top++; return 1; } }
出栈StackPop(SeqStack *S,DataType)
int StackPop(SeqStack *S,DataType) //取出顺序堆栈S的栈顶元素值由参数d带回，出栈成功则返回1，否则返回0 { if(S->top<=0) { printf("堆栈已空无数据元素出栈！\n"); return 0; } else { S->top--; //得注意top--，--top的差别 *d=S->stack[S->top]; return 1; } }
取栈顶数据元素StackTop(SeqStack S,DataType *d)
int StackTop(SeqStack S,DataType *d) //取栈顶数据元素值由参数d带回，成功返回1，不成功返回0 { if(S.top<=0) { printf("堆栈已空！\n"); return 0; } else { *d=S.stack[S.top-1]; return 1; } }
撤销动态申请空间Destory(SLNode *head)
void Destory(SLNode *head) { LSNode *p,*p1; p=head; while(p!=NULL) { p1=p; p=p->next; free(p); } }
