循环队列概念、设计设计及错误溢出现象说明VS C语言实例

1.错误的顺序队列溢出和循环队列概念

我们已经了解了队列的基本数据结构。对于顺序队列来说，它的存在足以解决大部分设计问题，但是它仍然存在一些缺陷和不足，因为我们的入队和出队操作是要连接和移除它后面直接的节点，让其在可利用的空间中不断走向队列的一侧，这会导致错误溢出。

什么是假溢出？例如：

（顺序队列示例）

让我们看看队列的本质。首先我们有一个顺序队列。这个队列的大小是5，已经包含了四个元素data1,data2,data3,data4，然后我们将队列出列，我们出列了2个元素，队列看起来是这样的：

看起来没有问题。此时我们将执行入队操作并入队2个元素，它们是data5和data6。这时我们就发现了问题。尾指针已移出我们可以执行队列操作的范围。我们称之为队列的存储空间没有满，而是队列已经溢出了。我们称这种现象为“假溢出”。

（出队时出现虚假溢出）

也许此时会出现一个问题。我们研究的队列不就是一个使用链表实现的动态队列吗？当没有空间时，就会产生空间。这会导致假溢出吗？

是的，确实，动态创建队列时，只是继续向后申请内存空间。即使之前的出队操作释放了之前的位置，指针仍然会向后移动，直到达到系统为程序分配的内存上限，才被强制终止，这对于操作极其频繁和排队的程序来说是致命的。此时我们需要优化我们的队列，使用更完美的结构——循环队列。

循环队列的思想很简单，就是根据原队列给定我们的队列大小的范围，如果队列后部已满，则从队列前部开始插入。队列来达到空间复用的效果，因为循环队列的设计思想更像是一个环，所以常常用圆图来表示，但注意它并不是真正的圆，循环队列仍然是单线性的。

2。循环队列结构设计

由于循环队列指定了数据范围的大小，因此不需要使用链式动态创建方式（如果仍然使用链式存储，将无法确定何时创建）返回队列头进行插入操作），所以我们会使用如图所示的模拟方法：

其中，data代表一个数据数组，int是一个类型，可以修改为任意自定义类型，比如如简单的Char、float类型等，也可以是复杂的结构类型。我们用maxsize来表示循环队列的最大容量，它代表了队列的整个操作空间。

rear代表进入队列时移动的尾部指针。

正面代表出队时移动的头指针。

代码可以表示为