1、第三章 栈 和 队列3.1 栈3.2 栈的应用举例*3.3 栈与递归的实现3.4 队列*3.5 离散事件模拟从数据结构的角度看 : 栈、队列和线性表相同从数据类型的角度看 : 栈、队列和线性表不同ListInsert(L, i, e) (1i n+1) ListInsert(S, n+1, e) ListDelete(L, i， e)(1i n)ListDelete(S, n) ana2 a1表头为 栈底 表尾为 栈顶a1a2an栈底栈顶ana2 a1n 只允许在一端插入和删除操作的只允许在一端插入和删除操作的线性表线性表 .n 允许插入和删除的一端允许插入和删除的一端称为称为 栈顶栈顶 (t
2、op)， 另一端另一端称为称为 栈底栈底 (base)n 特点特点 : 后进先出后进先出 (LIFO)3.1 栈栈 ( Stack )退栈 进栈a1anan-1topbaseADT Stack 数据对象 ： D ai |aiElemSet,i =1,2,.,n, n0 数据关系 ： R1 |ai-1,aiD, i=2,.,n 约定 an 端为栈顶， a1 端为栈底 。基本操作 ：InitStack(/存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量typedef struct SElemType *base; /栈底指针SElemType *top; /
3、栈顶指针int stacksize; /当前已分配的存储空间 ,以元素为单位 SqStack;空栈 :S.base=S.top(初始化状态 )toptopabasebctop detop栈满 :S.top-S.base=S.stacksizebase若栈结构不存在， base为 NULL栈顶指针始终是指在栈顶元素的后面一个位置栈顶指针始终是指在栈顶元素的后面一个位置顺序栈的初始化操作Status InitStack(SqStack if (!S. base) exit(OVERFLOW); / 存储分配失败S.top = S.base ;S.stacksize = STACK_INIT_SIZ
4、E ; / 初始存储容量return OK; / InitStack获取栈顶元素操作Status GetTop(SqStack S, SElemType 否则返回 ERRORif (S.top = S.base) return ERROR;e=*(S.top-1);return OK; /GetTop进栈操作Status Push(SqStack if (!S.base) exit(OVERFLOW); / 存储分配失败S.top =S.base+S.stacksize;S.stacksize +=STACKINCREMENT;*S.top = e; S.top+ ;return OK; /Push
