数据结构与算法——第3章-什么是循环队列(3.6.3)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
1.顺序队列的弊端
2.什么是循环队列

二 顺序队列的弊端

1
2
3
4
前面讲顺序队列的时候提到，顺序队列的实现方案并不完美，存在以下两个弊端：
1.随着元素的入队和出队，队列整体向顺序表的尾部移动，队列左侧的空闲空间无法再次利用；
2.当队列移动到顺序表尾部时，新元素将无法入队。
接下来，我教大家对顺序队列进行改良，彻底消除以上两个弊端，改良后的顺序队列又称循环队列。

三 什么是循环队列

3.1 概念

1
2
所谓循环队列，本质仍是用顺序表模拟实现队列，
只不过在具体实现的过程中，会将顺序表想象成首尾相连的环状表来用。

3.2 图示

1
2
例如，图 1 左侧就是一个空的 "环状" 顺序表，用它模拟实现队列，队头（top）和队尾（rear）都位于 a[0] 处。
图 1 右侧是一个存有 {1,2,3,4} 的循环队列，它的队头位于 a[2] 处，队尾位于 a[6] 处

图示

3.3 注意点

1
2
再次强调，我们只是将顺序表想象成环状表来用，实际用 C 语言程序实现循环队列时，
建立的仍是普通的顺序表，后续会讲解将顺序表当做环状表使用的实现方法。

3.4 说明

1
2
3
4
5
6
7
在环状顺序表中，最后一个位置（a[6]）和第一个位置（a[0]）紧挨着，这样做的好处是：

1.随着元素做入队和出队操作，整个队列也只会在环状表中 "绕圈圈"，不存在队列整体向顺序表尾部移动的问题，
顺序表的空间可以充分利用；
2.不存在“假溢出”的问题，当队列中的元素占满整个顺序表时，新元素入队会发生“真溢出”错误。

你看，循环队列确实消除了顺序队列的两个弊端。