环形队列算法（环形队列原理）

科技前沿 • 2025-04-30 23:24 • 阅读 37

大家好，我是讯享网，很高兴认识大家。

 <p>环形队列是在实际编程极为有用的数据结构,它有如下特点。</p>

它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。

因为有简单高效的原因，甚至在硬件都实现了环形队列.

环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列.

一.环形队列实现原理

------------------------------------------------------------

内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。

因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。

为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。

环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.

如何判断环形队列为空，为满有两种判断方法。

一.是附加一个标志位tag

二.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。

队列空： head==tail
队列满： (tail+1)% MAXN ==head

二.附加标志实现算法

-------------------------------------------------------------

采用第一个环形队列有如下结构

讯享网

初始化状态: q->head = q->tail = q->tag = 0;

队列为空:( q->head == q->tail) && (q->tag == 0)

队列为满 : ((q->head == q->tail) && (q->tag == 1))

入队操作:如队列不满，则写入

q->tail = (q->tail + 1) % q->size ;
出队操作：如果队列不空，则从head处读出。

下一个可读的位置在 q->head = (q->head + 1) % q->size

完整代码

头文件ringq.h

实现代码 ringq.c

讯享网

测试代码

三.预留空间环境队列

-------------------------------------------------------------------

不采用tag,只留一个空间

初始化状态: q->head = q->tail = q->tag = 0;

队列为空:( q->head == q->tail)

队列为满 : (((q->tail+1)%q->size) == q->head )

入队操作:如队列不满，则写入

q->tail = (q->tail + 1) % q->size ;
出队操作：如果队列不空，则从head处读出。

下一个可读的位置在 q->head = (q->head + 1) % q->size

头文件

ringq.h

讯享网

实现代码ringq.c

作者： Andrew Huang

讯享网