第3章 栈和队列（二） 1/.

Presentation on theme: "第3章 栈和队列（二） 1/."— Presentation transcript:

1 第3章 栈和队列（二） 1/

2 内容回顾 栈的定义及特点 顺序栈的类型定义 顺序栈进栈操作int Push( SqStack *S, SElemType e)
顺序栈出栈操作 链栈与链表的区别 2/

3 队列 教学目标 教学内容 掌握队列的定义和特点 掌握队列的存储结构及其基本操作实现 队列的定义 循环队列—队列的顺序表示和实现
链队列—队列的链式表示和实现 3/ 计算机科学与技术系 信息与教育技术中心

4 1.队列的定义 定义 特点 队列是只允许在表的一端进行插入，在表的另一端进行删除的线性表。 队尾(rear)——允许插入的一端
队头(front)——允许删除的一端 特点 先进先出(FIFO, First In First Out) 4/

5 1.队列的定义 双端队列 a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an)
端1 端2 入队 出队 5/

6 练习 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。 B （A）2 （B） （C）4 （D）6 2018年12月4日

7 1.队列的定义 队列的基本操作 构造空队列 入队 出队 取队头元素 判队列是否为空 置空队 队列的抽象数据类型定义 P73 7/

8 2.循环队列——队列的顺序表示和实现 队列的顺序存储结构 #define MAXQSIZE 100 //最大长度
Typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue; 2018年12月4日

9 2.循环队列——队列的顺序表示和实现 队头和队尾指针在队列初始化时均置为指向数组空间的下界 —０。 队头指针指向当前队头元素。
队尾指针指向当前队尾元素的下一个位置。 9/

10 2.循环队列——队列的顺序表示和实现 SqQueue Q; Q.rear 1 2 3 4 5 1 2 3 4 5 J1 J2 J3
1 2 3 4 5 J1 J2 J3 Q.rear 1 2 3 4 5 1 2 3 4 5 J6 J5 Q.rear Q.front J4 Q.front J3 J2 Q.front=0 Q.rear=0 Q.front J1 队空 J1,J2,J3入队 J1,J2,J3出队 J4,J5,J6入队 10/

11 2.循环队列——队列的顺序表示和实现 存在问题 解决方案 设数组长度为M，则： 循环队列
当Q.front=0, Q.rear=M-1时，再有元素入队发生溢出——真溢出 当Q.front0,Q.rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 循环队列 基本思想：把队列设想成环形，让Q.base[0]接在Q .base[M-1]之后，若Q. rear+1==M，则令Q. rear=0; 11/

12 2.循环队列——队列的顺序表示和实现 实现 利用“模”运算
入队： Q .base[Q. rear]=x; Q. rear=(Q. rear+1)%M; 出队： x=Q .base [Q. front]; Q. front=(Q. front+1)%M; 队满、队空判定条件 M-1 1 Q. front Q. rear …... 12/

13 队满：(Q. rear+1)%M== Q. front
队空： Q. front== Q. rear 队满： Q. front== Q. rear 1 2 3 4 5 Q. rear Q. front J4 J5 J6 1 2 3 4 5 Q. rear Q. front 初始状态 J4,J5,J6出队 J7,J8,J9入队 J4 J5 J6 1 2 3 4 5 Q. rear Q. front J9 J8 J7 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空： Q. front== Q. rear 队满：(Q. rear+1)%M== Q. front 13/

14 2.循环队列——队列的顺序表示和实现 初始化空队列 Status InitQueue(SqQueue *Q){
Q->base=(QElemType *)malloc(MAXQSIZE *sizeof(QElemType)); if(!Q->base) exit(OVERFLOW); Q->front = Q->rear = 0; return OK; } 14/

15 2.循环队列——队列的顺序表示和实现 Status EnQueue(SqQueue *Q,QElemType e) { 入队算法
if( (Q->rear+1)%MAXQSIZE == Q->front ) // 队列满 return ERROR; Q->base[Q->rear] = e; Q->rear=(Q->rear+1)%MAXQSIZE; return OK;} 15/

16 2.循环队列——队列的顺序表示和实现 出队算法 Status DeQueue(SqQueue *Q, QElemType *e) {
if(Q->front == Q->rear) // 队列空 return ERROR; * e = Q->base[Q->front]; Q->front = (Q->front+1)%MAXQSIZE; return OK; } 16/

17 2.循环队列——队列的顺序表示和实现 求队列长度算法 int QueueLength(SqQueue Q) {
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } 17/

18 3.链队列—队列的链式表示与实现 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。
显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。 18/

19 . data next 队头 队尾 Q.front Q.rear 19/

20 3.链队列—队列的链式表示与实现 队列的链式存储结构 typedef struct QNode{ typedef struct{
QElemType data; struct QNode *next; } QNode ，*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; 20/

21 3.链队列—队列的链式表示与实现 链队列是否需要头结点？ 如何判断队空？
为了操作的方便，在链队列中也添加一个头结点，并使队头指针指向头结点。 如何判断队空？ 队空条件为 Q.front == Q.rear 链队列在进队时无队满问题 21/

22 3.链队列—队列的链式表示与实现 队列 初始化操作 Status InitQueue(LinkQueue *Q){
if( !(Q->front=Q->rear=(QueuePtr)malloc (sizeof(QNode)))); exit(OVERFLOW); Q.front->next=NULL; return OK; } 空队列 22/

23 3.链队列—队列的链式表示与实现 入队列操作 元素x入队列 元素y入队列
Status EnQueue(LinkQueue *Q, QElemType e){ QueuePtr p; if( !(p=(QueuePtr)malloc(sizeof(QNode))) ) exit(OVERFLOW); p->data = e; p->next = NULL; Q->rear->next = p; Q->rear = p; return OK; } 元素x入队列 元素y入队列 23/

24 3.链队列—队列的链式表示与实现 出队列操作 Status DeQueue(LinkQueue *Q, QElemType *e) {
QueuePtr p; if( Q->front == Q->rear ) return ERROR; p = Q->front->next; e = p->data; Q->front->next = p->next; if(Q->rear == p) Q->rear = Q->front; free(p); return OK; } 元素x出队列 元素y出队列 24/

25 3.链队列—队列的链式表示与实现 队列判空操作 Status QueueEmpty(LinkQueue Q) {
if(Q.front == Q.rear) return TRUE; else return FALSE; } 空队列 25/

26 小结 队列的定义及特点 循环队列结构类型定义及基本操作（初始化、入队、出队、求长度） 链式存储结构类型定义及基本操作 26/

27 作业 设用一个单向循环链表来表示队列（也称链式循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的初始化、入队列和出队列操作。 实验三：队列的操作及应用 27/