C数据结构：循环队列的顺序存储结构_设计循环队列存储结构

队列的定义

声明： 本篇博客是实现循环队列。

定义

记住队列是先进先出，FIFO——first in first out，
（和栈的区别也是这个，栈是一头开一头闭，就像一个瓶子，先进的后出）
队列就是两头开，但是当队列用于顺序存贮的时候很容易造成假溢出。

假溢出

假设在队满的，但是尾指针指向的是比队列空间的大小还要大一个位置，所以称之为假溢出，这也是造成空间浪费的一个缺点。

空间浪费的缺点

因为队列是先进先出，所以在队头出队，当队头指针和队尾指针指向的位置一样的时候就表示全部出队成功，但是队头以前指向的空间就无法得以继续利用，就造成了空间浪费。

如何解决

这时候假设我们已经队满了，若想要继续录入信息，大家肯定能想到的是回到头指针的位置继续录入信息。
那么一个叫循环队列的算法解决了这个问题，其实就是用指针让队列形成一个闭环，这样既控制了空间的大小，又防止了出栈时候的空间浪费，因为只要有这两个指针在，按顺序录入的时候总能有一个空间给你录入。

循环队列的缺点

其实与其说是缺点，不如说是程序员不应该选择这个循环队列的算法。缺点就是当队列满队了时候，继续录入信息，我们知道队列的尾部指针会重新指向头部指针，这时候就会造成你前面录入的信息丢失，被新录入的信息覆盖掉。

主要的算法思想（重要）

循环队列可以把他想象成小时候经常看到的幸运转盘，按一个方向旋转，所以进队的时候也是按一个方向进，只是把一个顺序队列用一个算法使之成为看似循环的一个队列。

如何理解循环队列（必看）

这里rear是尾部，front是头部，但是我这个不同的是使用尾进尾出的方式，和其他博客有点不一样，我单纯觉得这样比较好理解。

首先分为三个部分
第一部分： 进队
第二部分： 出队
（在你队满了的时候，若还想继续录入信息，进入下一步）
第三部分： 队头移动+1个位置，在队满的情况下+1会造成假溢出，也就是队头队尾相撞了，那么这时候队尾也进行一个+1的操作，这样就实现了队头队尾一直处于连在一起的形式，也就是形成了循环队列。

（ ↓ 考虑的因素 ↓ ）
队列还没满的时候想出队的话，也不用担心这个算法会出错，因为你出队的时候也包含在了队头+1移动的操作，第三部的算法肯定能满足这个条件，现在我总是不禁感叹前辈们的智慧，太妙了。

***如果看到这也不懂的话，恕我无力回天。 ***

结构体代码

/*单词顺序表*/
typedef struct _Elem{
	char *word;//存放单词 
	int lenth; 
	int front;
	int rear;
}Elem; 
Elem *temp = NULL;
1
2
3
4
5
6
7
8

两种实现方法

①循环队列，队头和队尾指针连在一起的形式。

（这个方法理解了，那么等下将第二个方法的时候就比较容易理解。）

首先解释一下下面的代码以便理解：
temp结构体，存字符进word这个字符数组里面，word就是一个循环队列，
我们现在是要实现不浪费一个空间写出一个循环队列。

第一个字符进队前，rear和front在同一个位置，但是这时候不能移动空间，因为如果移动了，第一个位置就没有存到信息，所以要再用一个temp->lenth作为判断条件，这个的意思就是当你还没有录入字符的时候，不能进入if语句把front指针进行移动。

下面开始进队，进队的时候把尾部指针rear进行移动+1，所以这时候rear和front指针位置开始不一样了， 这一点很重要，如果没有这步，会直接导致后面的错误。

接下来就是把lenth进行自加，用来记录录入了多少个字符，但是由于该队列是循环队列，不能超过MAXSIZE空间，所以也要一个 限制的大小条件，

#1#： 这时候如果你继续进队，回到第一步的代码里面，进行第二个字符录入，现在可以知道rear和front的位置不一样，所以即使lenth不等于零也无法进入if语句对front指针向前移动+1，←这个是循环队列实现的算法精髓 。
往后就是一直录入，直到rear = (rear + 1)%MAXSIZE;
#2#： 这个语句运行完成后，变成队满状态了，这时候rear和front 同时% MAXZSIZE ←这也是循环队列实现的算法精髓

不会改变你rear和front的位置关系，所以他们队满的时候他们是相等的，如此来
%MAXSIZE不仅不会造成空间溢出，
rear%MAXSIZE ==front%MAXSIZE && temp->lenth!=0中个条件判断将front向前+1移动的操作 把该队列变成了一个循环队列

下面是伪代码：

if(rear ==front%MAXSIZE && temp->lenth!=0) 
	front = (front+1)%MAXSIZE;

	temp->word[rear] = ch;
	rear = (rear + 1)%MAXSIZE;


if(temp->lenth < MAXSIZE)
{
	temp->lenth++;
} 
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

②浪费一个空间形成循序队列

这个的思想就是不用像第一种方法一样要用一个lenth条件来判断是否已经录入一个字符了，这个方法就是简单粗暴的形式，浪费一个空间来使之直接形成循环队列。

代码区别：
if的判断语句变成了 rear%MAXSIZE ==(front+1)%MAXSIZE，去掉了lenth这部分的代码

具体实现如下：

if(rear ==(front+1)%MAXSIZE) front = (front+1)%MAXSIZE;
	temp->word[rear] = ch;
	rear = (rear + 1)%MAXSIZE;
1
2
3

③浪费多个空间

其实你理解了第二个思想的话，很简单就能举一反三，只要把所有的+1修改成+2就代表浪费两个空间，这样也能形成闭环，+3、+4只要按照你的需求来修改就可以，需要注意的是千万不能让你的数组越界，浪费几个空间就要保证你的数组空间足够给你去挥霍，不然程序就很容易越界崩溃掉。

结尾

看完后是不是觉得就几行代码就实现了这么强大的循环队列功能，其实我也是这么觉得的，但是真正理解起来确实一丢丢的时间。

注：本博客主要用文字叙述的方式帮助理解，希望能帮助到各位。
因为我觉得文字叙述虽然比不上图表理解来得更快，但是文字叙述会比图表更能透彻的理解队列。所以如果希望各位耐心读完。
（如有错误请私信我，如果确实有错，到时候我可以直接修改喔~）