数据结构（3） 栈和队列
http://jpkc.jnu.edu.cn/sjjg/upload/jiaoyan/
数据结构（3） 栈和队列
从数据类型的角度看：它们和线性表不同
线性表 Insert(L,i,x)(1<=i<=n+1) Delete(L,i)(1<=i<=n)
栈 Insert(S,n+1,x) Delete(S,n)
队列 Insert(Q,n+1,x) Delete(Q,1)
栈的类型和定义
ADT Stack {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{
约定an 端为栈顶，a1 端为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALE。
StackLength(S)
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop(S, &e)
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push(&S, e)
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S, &e)
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
} ADT Stack
栈的应用举例：数制转换 括号匹配的检验 行编辑程序 迷宫求解 表达式求值