数据结构 第3章 栈和队列

1、22.3.322.3.322.3.322.3.322.3.322.3.3ADT Stack 数据对象数据对象： D = ai | aiElemSet, i=1,2,n, n0 数据关系数据关系：R1 = | ai-1, aiD, i=2,3,n 约定约定an端为栈顶端为栈顶 , a1端为栈底。端为栈底。基本操作：基本操作：ADT Stack22.3.322.3.3基本操作：InitStack( &S )DestroyStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)ClearStack(&S)Push(&S,

2、e)Pop(&S,&e)StackTraverse(S,visit()22.3.322.3.3uInitStack( &S )操作结果：构造一个空栈。操作结果：构造一个空栈。uDestroyStack(&S)初时条件：栈初时条件：栈S已存在已存在操作结果：栈操作结果：栈S被销毁被销毁uStackEmpty(S)初时条件：栈初时条件：栈S已存在已存在操作结果：若栈操作结果：若栈S为空栈，则返回为空栈，则返回TRUE,否否则则FALSE。22.3.322.3.3uStackLength(S)初时条件：栈初时条件：栈S已存在已存在操作结果：返回操作结果：返回S的元素个

3、数，即栈的长度。的元素个数，即栈的长度。uGetTop(S,&e)初时条件：栈初时条件：栈S已存在且非空。已存在且非空。操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。uClearStack(&S)初时条件：栈初时条件：栈S已存在已存在操作结果：将操作结果：将S清空为空栈清空为空栈22.3.322.3.3uPush(&S,e)初时条件：栈初时条件：栈S已存在已存在操作结果：插入元素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。uPop(&S,&e)初时条件：栈初时条件：栈S已存在且非空。已存在且非空。操作结果：删除操作结果：删除S的栈顶

4、元素，并用的栈顶元素，并用e返回返回其值。其值。uStackTraverse(S,visit()初时条件：栈初时条件：栈S已存在且非空已存在且非空操作结果：从栈底到栈顶依次对操作结果：从栈底到栈顶依次对S的每个数的每个数据元素调用函数据元素调用函数visit()。一旦。一旦visit()失败，失败，则操作失败。则操作失败。22.3.322.3.322.3.322.3.322.3.322.3.3空栈空栈basebasetoptop元素元素a进栈进栈basebasetoptopa元素元素b，c进栈进栈basebasetoptopabc元素c退栈basebasetoptopabbasebasetop

5、topabdef元素d，e，f进栈22.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.3 （ div为整除运算为整除运算, ,mod为求余运算为求余运算 ）22.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.

6、3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.3a1 , a2 , , an出队出队入队入队队尾队尾队首队首22.3.322.3.3数据对象数据对象： D = ai | aiElemSet, i=1,2,n, n0 数据关系数据关系：R1 = | ai-1, aiD, i=2,3,n 约定其中约定其中a1 端为对列头端为对列头 , an端为队列尾。端为队列尾。基本操作：基本操

7、作：22.3.322.3.3基本操作：InitQueue( &Q )DestroyQueue (&Q )QueueEmpty(Q )QueueLength(Q )GetHead(Q , &e)ClearQueue (&Q )EnQueue (&Q,e)DeQueue (&Q,&e)Queue(Q,visit()22.3.322.3.3GetHead(Q , &e)初时条件：初时条件：Q为非空队列。为非空队列。操作结果：用操作结果：用e返回返回Q的队头元素的队头元素DeQueue (&Q,&e)初时条件：初时条件：Q为非空队列。为非空队列。操作结果：删除操作结果：删除Q的队头元素，并用的队头元素，并用e返回返回其值。其值。EnQueue (&Q,e)初时条件：队列初时条件：队列Q已存在已存在。操作结果：插入元素操作结果：插入元素e为为Q的新的队尾元素。的新的队尾元素。22.3.322.3.322.3.322.3.322.3.322.3.3(a) 空队列空队列front rear(b) x入队入队 x front rear(c) y再入队再入队 y front rear x(d) x出队出队 y xfront rear22.3.322