第三章 栈和队列 第二部分 队列(Queue) 2019/4/8.

Presentation on theme: "第三章 栈和队列 第二部分 队列(Queue) 2019/4/8."— Presentation transcript:

1 第三章 栈和队列 第二部分 队列(Queue) 2019/4/8

2 3.2 队列 逻辑结构：先进先出(FIFO) 只能在一端插入、另一端删除的线性表 队尾(rear)：允许插入的一端
队头(front)：允许删除的一端 a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1, a2, ……, an) 2019/4/8

3 队列实现 链队列：单链表 结点定义 typedef struct QNode { QElemType data;
队首指针 front：指向头结点 队尾指针 rear：指向队尾元素 头结点 ^ …... front 队头 队尾 rear 结点定义 typedef struct QNode { QElemType data; struct QNode *next ; } QNode , *QueuePtr ; 队列定义 typedef struct { QueuePtr front , rear ; } *LinkQueue ; 2019/4/8

4 空队 ^ q.front q.rear x x入队 ^ q.front q.rear y入队 x y q.front q.rear ^
2019/4/8

5 ******队列基本操作算法******
单链队列的基本操作 建立空队列 Status InitQueue(LinkQueue &Q){ //构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 return OK; } Q.front->next=NULL; 2019/4/8

6 单链队列的基本操作--------销毁队列
Status DestroyQueue(LinkQueue &Q){ //销毁队列Q while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK; 2019/4/8

7 Status EnQueue ( LinkQueue Q , QElemType e) { QueuePtr p ;
入队算法 Status EnQueue ( LinkQueue Q , QElemType e) { QueuePtr p ; p=(QueuePtr) malloc ( sizeof ( QNode ) ); p->data = e ; p->next = NULL ; Q->rear->next = p; Q->rear = p ; return OK ; } 2019/4/8

8 Status DeQueue (LinkQueue Q , QElemType &e) { QueuePtr p ;
出队算法 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 ( p->next = = NULL) Q->rear = Q->front ; free(p); return OK ; } 当队列尾元素被删除后，队尾指针也丢失 因此需要给队尾指针重新赋值：指向头结点 2019/4/8

9 队列的顺序存储结构 一维数组：base [MAXQSIZE] 5 4 3 2 1 front = 0 rear = 0 队空 约定：
队空 (动态分配数组空间)： typedef struct { QElemType *base ; //数组 int front , rear ; //队首，队尾(元素下标) int queuesize; //最大元素个数 } SqQueue , *SeqQueue ; 约定： rear：队尾元素后一位置 front：队头元素 初值 front = rear = 0 2019/4/8

10 队列的顺序存储结构 一维数组：base [MAXQSIZE] 5 5 4 4 rear 3 3 rear J3 2 2 rear J2 1
front = 0 rear = 0 1 2 3 4 5 队空 J1,J2,J3入队 1 2 3 4 5 front rear rear J3 rear J2 rear J1 入队列：base [ rear++] = e ; 2019/4/8

11 出队列：e= base[front++];
队列的顺序存储结构 一维数组：base [MAXQSIZE] 1 2 3 4 5 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear rear front J3 front J2 front J1 front J1,J2,J3出队 出队列：e= base[front++]; 2019/4/8

12 存在问题 设数组尺寸 M (＝6) 当front = 0 , rear = M 时，再有元素入队发生溢出——真溢出 rear 1 2 3 4
5 J1,J2,J3,J4,J5,J6入队 J4 J5 J6 front J1 J2 J3 J7入队？ 如何解决？ 扩充空间 2019/4/8

13 存在问题 设数组尺寸为 M，则： 当front  0 , rear = M 时，再有元素入队发生溢出——假溢出 rear 1 2 3 4
5 J1,J2,J3出队 J4 J5 J6 front J7入队？ 如何解决？ 扩充空间？ front 以前的空闲空间被浪费！ 2019/4/8

14 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 J1出队? 5 4 rear 3 J3 2 J2 1 front
J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear J1出队? 2019/4/8

15 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2
1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 J2 front front＋＋？ J1出队 2019/4/8

16 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2
1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 J2 元素下移 front front 不动！ J1出队 2019/4/8

17 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2
1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 front J2 front 不动！ J1出队 2019/4/8

18 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2
J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 元素下移 front J2 front 不动！ J1出队 2019/4/8

19 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear rear -- 3 3 J3 2
J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear rear -- J3 front J2 front 不动！ J1出队 2019/4/8

20 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear -- 3 3 rear J3 2
J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear -- rear J3 front J2 front 不动！ J1出队 2019/4/8

21 “假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 元素移动费时！ 能否不移动元素？ 5 5 4 4 rear 3 3
J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 front J2 J1出队 元素移动费时！ 能否不移动元素？ 2019/4/8

22 “假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ base [ rear] = ‘J6’; rear 1 2 3 4 5
J4 J5 front J6入队 J6 base [ rear] = ‘J6’; 2019/4/8

23 “假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ base [ rear] = ‘J6’; rear ++;
1 2 3 4 5 J6 base [ rear] = ‘J6’; J5 rear ++; (rear = 6) front J4 下标将越界！(队尾将超出数组) 令其返回数组前面空闲单元 0 (rear = 0;) 2019/4/8

24 “假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分
若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 J5 front J4 rear J7入队？ J1,J2,J3出队 2019/4/8

25 “假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分
若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 J5 front J4 rear J7 J1,J2,J3出队 2019/4/8

26 “假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分 在 J6 入队时：
若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 在 J6 入队时： if ( rear ++ > M ) rear = 0; else rear ++ ; J5 front J4 rear J7 J1,J2,J3出队 2019/4/8

27 “假溢出”的解决方案 II 循环队列 设想队列成环形，让base[0]接在base[M-1]之后 入队：
if ( rear ++ > M ) rear = 0; else rear ++ ; M-1 1 front rear …... 求模(求余)运算 入队： base[rear]=e; rear=(rear+1)%M; 出队： e=base[front]; front=(front+1)%M; 队满、队空判定条件? 2019/4/8

28 队空：front==rear 队满：front==rear
1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 front J4,J5,J6出队 J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 rear 一般情况 如何区分队空、队满？ 2019/4/8

29 J5 front J4,J5,J6出队 front J6 J4 rear front rear J7,J8,J9入队 J5 J6 J4
1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 J4,J5,J6出队 front J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 rear 一般情况 解决方案： 1、另外设一个标志以区别队空、队满 2019/4/8

30 J5 front J4,J5,J6出队 front J6 J4 rear front J7,J8,J9入队 J5 J6 J4 rear
1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 J4,J5,J6出队 front front J7,J8,J9入队 J5 J6 J4 5 rear 一般情况 4 3 1 解决方案： 1、另外设一个标志以区别队空、队满 2、少用一个元素空间： 队空：front == rear 队满：(rear+1) % M == front 2 J7 J8 rear J9 入队时，已满！ 2019/4/8

31 优先队列 (Priority Queue) 优先队列：每次从队列中取出的是具有最高优先权的元素 例：任务的优先权及执行顺序的关系
数字越小，优先权越高 2019/4/8

32 小 结 队列的插入运算在表的一端进行，而删除运算却在表的另一端进行。
小 结 队列的插入运算在表的一端进行，而删除运算却在表的另一端进行。 根据队列的这一特点，在使用顺序存储结构时，用了环形队列，这样可解决假溢出问题，但要特别注意队列满和队列空的条件及描述。 2019/4/8