环形队列的实现（实现环形队列的各种基本运算的算法）



​ 队列是一种特殊的线性表，从逻辑结构上看，队列仍然是线性表的一种，其特殊性主要体现在其基本运算有着特殊的限定。实际应用中有很多先到先得的问题，需要按先后顺序取解决，比如排队购物，食堂排队取餐等，计算机解决这类问题需要用到队列来解决。

​ 队列限定了线性表中的数据元素的插入和删除操作必须分别在线性表的两端进行，访问次序是先进先出。

队列的定义

​ 队列是一种特殊的线性表，其特殊性体现在对数据元素的插入和删除操作的限定。

​ 队列的特点是先进先出（First In First Out，FIFO），即第一个进入队列的数据元素将第一个被删除。

​ 队列的插入操作称为入队，队列的删除操作称为出队。队列的插入操作只能在队尾进行，队列的删除操作只能在队首进行。

​ 为最先进入队列的数据元素，也将最先被访问，最先出队列，而为最后进入的数据元素，也将最后被访问，最后出队列。

​ 队列可以用于许多问题的求解，比如医院排队挂号、飞机检票进站、排队乘车、作业调度等，常用它来模拟求解。

---

队列的抽象类型

队列的顺序存储结构

线性表有顺序存储和链式存储，栈是线性表，具有这两种存储方式。同样’队列作为一种特殊的线性表，也同样存在这两种存储方式。我们先来看队列的顺序存储结构。

顺序存储队列的主要不足在于它可能遇到“假溢出”的情况，即数组虽然还有空间，但由于队列的头尾指针的处理方式，导致无法继续添加元素。下面通过一个简单的图示来解释这个问题。

假设我们有一个固定大小为5的数组来存储队列：

队列的头指针（front）指向队列的第一个元素，尾指针（rear）指向队列最后一个元素的下一个位置。现在我们依次入队元素1, 2, 3, 4, 5：

此时队列已满，无法再添加新的元素。接下来我们出队元素1, 2：

现在，虽然数组的前两个位置是空的，但由于我们的头指针（front）已经移动到了索引1的位置，我们无法将新元素添加到索引0的位置。如果我们继续出队元素3, 4, 5：

此时，虽然数组看起来是空的，但实际上我们已经无法使用索引0和1的位置了，因为头指针（front）和尾指针（rear）的处理方式不允许我们在这两个位置插入新元素。这就是所谓的“假溢出”，即数组还有空间，但由于队列的实现方式，我们无法使用这些空间。

就像坐地铁，后一段的位子没了我们还应该往前看看。

所以循环队列应运而生。

循环队列

我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。故而有：

队列的初始化，,都指向0;

1，2，3，4元素依次入队，还未溢出，跟普通的队列此时一样，指向下标为4的地方，标志着下一个元素进入队列时的位置。

1，2元素从队列中出队，指针向后移动，指向下标为2的地方，标志着下一个出队的元素位置。

向队列中增加元素5，其从队尾加入，此时由于，导致可以被取余，使得，指向的是下标为0的地方。

如果这个时候我们再往队列加入元素6，7，会发现.两个指针指向同一个地方，我们发现跟初始化队列的时候一样。这个时候我们难以判断到底是初始化了这个队列还是满的队列，所以我们这时候退而求其次，我们只要实现这个功能就行了，不要要求那么多了。

所以有：

牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志。

此时我们判断队满条件是为：

其他方法解决判定队满的方法:

方法1：类型中增设表示元素个数的数据成员。这样，队空的条件为

队满的条件为：

tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；

tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。

由于篇幅问题，我会另外开一篇这两种方法如何实现入队出队。

队列顺序存储的实现

存储结构代码：

循环队列初始化：

求其长度：

循环队列入队：

1. 检查队列是否已满。如果队列已满，入队操作失败。
2. 将新元素添加到队尾指针（rear）所指的位置。
3. 更新队尾指针，使其指向下一个可用的位置。如果队尾指针已经到达队列的末尾，将其重置为队列的起始位置。

出队：

1. 检查队列是否为空。如果队列为空，出队操作失败。
2. 从队头指针（front）所指的位置移除元素。
3. 更新队头指针，使其指向下一个元素的位置。如果队头指针已经到达队列的末尾，将其重置为队列的起始位置。

队列链式存储的实现

存储结构代码：

入队代码：

出队代码：

在上述代码中，我们定义了一个循环队列 Queue，并实现了入队 EnQueue 和出队 DeQueue 操作。在实际应用中，我们可以根据具体需求扩展队列的功能，例如增加队列长度的动态调整、支持优先级队列等。

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列的操作遵循先进先出（FIFO）的原则，即第一个进入队列的数据元素将第一个被删除。

队列的抽象数据类型定义了一系列操作，包括初始化队列、销毁队列、清空队列、判断队列是否为空、获取队列的队头元素、入队操作和出队操作等。

队列的顺序存储结构使用数组来实现，通过front和rear指针来指示队列的头和尾。在顺序存储队列中，可能会出现“假溢出”的情况，即数组虽然还有空间，但由于队列的头尾指针的处理方式，导致无法继续添加元素。

为了解决“假溢出”问题，可以使用循环队列的方式来实现队列的顺序存储。循环队列通过将数组的首尾相连，使得队列的头尾指针可以在数组的两端循环移动，从而充分利用数组的空间。

到此这篇环形队列的实现（实现环形队列的各种基本运算的算法）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/36255.html