欢迎光临散文网 会员登陆 & 注册

【数据结构】数据结构实现 1.4:循环队列(C++版)

2023-03-17 00:53 作者:九霄星河  | 我要投稿

数据结构实现 1.4:循环队列(C++版)

  • 1. 概念及基本框架

  • 2. 基本操作程序实现

    • 2.1 入队操作

    • 2.2 出队操作

    • 2.3 查找操作

    • 2.4 其他操作

  • 3. 算法复杂度分析

    • 3.1 入队操作

    • 3.2 出队操作

    • 3.3 查找操作

  • 4. 完整代码

1. 概念及基本框架

通过第三节我们知道,数组队列 在出队操作中需要花费 O(n) 的时间复杂度,原因在于出队时需要移动大量元素。如果我们可以循环利用空间,那么问题就迎刃而解。所以,循环队列 应运而生。循环队列结构如下:
(这里为了直观,将队列绘制成环形,实际内存依旧是连续的内存块。)

循环队列的结构

首先循环队列作为队列的一种,基本特性和数组队列相同:
1.队列 有 队头 和 队尾 两端。
2.入队 操作只能从 队尾 进行,出队 操作只能从 队头 进行。
3.先 入队 的先 出队 ,即 先进先出(First In First Out),FIFO 。
还有一个隐含特性,队列可以自行 扩容(缩容),而不需要用户关心。
由上图结构可知,队空和队满时,队头和队尾都指向同一块内存。因为循环队列和动态数组有一定差异,所以对循环队列从底层重新进行了实现。首先,依旧使用一个由 纯虚函数 构成的 抽象类 作为一个接口来定义这些操作。具体代码如下:

下面从底层重新构建一个循环队列类。

这个类内部定义一个数组,为了兼容更多类型,这里使用了泛型的概念。然后定义了队列的容量、大小以及队头和队尾。同理,构造数组时,可以初始化队列的队列容量,(默认是10)队头和队尾都是0。
与动态数组类似,为了实现自行 扩容(缩容),类内部创建了一个 resize 函数来实现。

原理上与动态数组类似,这里的 取余 操作保证了循环。下面对各种基本操作进行了重写实现。

2. 基本操作程序实现

2.1 入队操作

入队操作时可能会调用 扩容函数 。

2.2 出队操作

出队操作时可能会调用 缩容函数 。

2.3 查找操作

同样的,队列只能获得队首元素,所以这里的查找操作也非常简单。

2.4 其他操作

为了保证正确输出,print 函数中也采用了 取余 操作。

3. 算法复杂度分析

3.1 入队操作

入队操作

最坏复杂度 O(1+n) 中第一个 1 是指元素移动操作,第二个 n 是指 resize 函数,以下同理。
入队可能会引发扩容操作,平均而言,每增加 n 个元素,会扩展一次,会发生 n 个元素的移动,所以平均下来是 O(1) 。

3.2 出队操作

出队操作

3.3 查找操作

查找操作

总体情况:

总体情况

通过第三节我们知道,数组队列操作的增、查都是 O(1) 级别的时间复杂度,而删是 O(n) 级别的时间复杂度,因为每次出队的都是队首元素,后面的元素需要一个个向前移动。而对于循环队列,不需要移动元素,所以增、删、查都是 O(1) 级别的时间复杂度,实现了对数组队列的优化。
注:队列并不提供改的操作。

4. 完整代码

抽象类 接口代码:

循环队列 代码:


【数据结构】数据结构实现 1.4:循环队列(C++版)的评论 (共 条)

分享到微博请遵守国家法律