数据结构-栈与队列课件.ppt

小 结 栈的概念，特点，抽象数据类型栈的定义 栈的顺序表示和实现，栈的链接表示和实现 栈的典型应用 数制转换 括号匹配的检验 表达式求值 栈与递归 队列的概念，特点，抽象数据类型队列的定义 队列的顺序表示和实现，队列的链接表示和实现 * * * 64片金片移动次数：264-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？ 一年大约，移完这些金片需要５８００多亿年 世界、梵塔、庙宇和众生都已经灰飞烟灭 …… ! 优点：结构清晰，程序易读 缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。 递归的优缺点 递归?非递归 3.4 　队列 　队列是一种先进先出(FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素 a1 a2 a3 an ... 入队列 队头 队尾 a1 a2 a3 an ... 队头 队尾 出队列 a1 a2 a3 an ... 队头 队尾 出队列 a1 a2 a3 an ... 队头 队尾 出队列 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。 （A）2 （B）3 （C）4 （D）6 练习 B 数据对象: 数据关系: 基本操作: (1) InitQueue (Q) //构造空队列 (2) DestroyQueue (Q) //销毁队列 (3) ClearQueue (S) //清空队列 (4) QueueEmpty(S) //判空. 空--TRUE, ADT Queue { 队列的抽象数据类型 (5) QueueLength(Q) //取队列长度 (6) GetHead (Q,e) //取队头元素, (7) EnQueue (Q,e) //入队列 (8) DeQueue (Q,e) //出队列 (9) QueueTraverse(Q,visit()) //遍历 }ADT Queue 队列的抽象数据类型 #define M 100 //最大队列长度 Typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue; 队列的顺序表示－－用一维数组base[M] 队列的顺序表示－－用一维数组base[M] Q.front 0 1 2 3 4 5 Q.rear Q.front Q.rear J 1 J 2 J 3 Q.front Q.rear J 3 Q.front Q.rear J 5 J 6 front=rear=0 空队标志：front= =rear 入队：base[rear++]=x; 出队：x=base[front++]; Q.front Q.rear J5 J6 Q.front 0 1 2 3 4 5 Q.rear J5 J6 J1 J2 J3 J4 存在的问题 设数组大小为M front=0 rear=M时 再入队——真溢出 front?0 rear=M时 再入队——假溢出 解决的方法－－循环队列 1 0 Q.rear Q.front ... ... base[0]接在base[M-1]之后 若rear+1==M 则令rear=0; 实现：利用“模”运算 入队： base[rear]=x; rear=(rear+1)%M; 出队： x=base[front]; front=(front+1)%M; J4 J5 J6 0 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 队空：front==rear 队满：front==rear 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front J4 J5 J6 0 1 2 3 4 5 rear front 0 1 2 3 4 5 front J4,J5,J6出队 rear 循环队列 #define MAXQSIZE 100 //最大队列长度