一、循环队列的定义
二、循环队列图示
三、循环队列使用规则
为解决队满和队空的判断条件相同。
我们 采用 损失一个单元不用的方法
即当循环队列元素的个数是MAXSIZE-1时，就认为队列已满（front指向空的单元）
这样循环队列的队满条件就变成 ：
(rear+1)%MAXSIZE==front
循环队列的队空条件依旧是：
front==rear
四、循环队列的代码
#define MAXSIZE 4
typedef int DataType;
typedef struct
{
DataType data[MAXSIZE]; //实际上只能存MAXSIZE-1 个数据
int front;
int rear;
}SeqQueue;
//损失一个单元不用，即当循环队列中元素个数是MAXSIZE-1时，就认为队列已经满了
//front指向那个不使用的单元
//循环队列的队满的条件就是(rear+1)%MAXSIZE==front
//队空的条件是 front==rear
//初始化队列
void InitQueue(SeqQueue* Q)//初始化队列函数
{
Q->front = Q->rear = 0;//指针初始化
}
//判断是否为空
int EmptyQueue(SeqQueue* Q)//判断队空函数
{
if (Q->front == Q->rear)//队列为空
return 1;
else
return 0;
}
//判断是否为满
int FullQueue(SeqQueue* Q)//判断队满函数
{
if (Q->front == (Q->rear + 1) % MAXSIZE)//队尾指针加上1，再取余MAXSIZE的值如果等于队头指针，说明队列为满
return 1;
else
return 0;
}
//入队操作
void InQueue(SeqQueue* Q, DataType x)//入队函数
{
if (FullQueue(Q))
{
printf("队列已满,无法继续入队\n");
return;
}
else
{
Q->rear = (Q->rear + 1) % MAXSIZE;//更新队尾指针rear,队尾指针加1再取余MAXSIZE,将数组形成一个循环
Q->data[Q->rear] = x;//将入队的数据放到队列数组，更新后的rear所指向的位置
}
}
//出队操作
void DeQueue(SeqQueue* Q)//出队函数
{
if (EmptyQueue(Q))
{
printf("队列已空,无法继续出队\n");
return;
}
else
{
Q->front = (Q->front + 1) % MAXSIZE; //更新队头指针front, 队头指针加1再取余MAXSIZE, 将数组形成一个循环
}
}
//取队头操作
DataType GetFront(SeqQueue* Q)//取队头函数
{
if (EmptyQueue(Q))
{
printf("队列已空,无队头元素\n");
return 0;
}
else
{
int t; //因为front指向的位置无元素，队头元素在front指向的后一位
t = (Q->front + 1) % MAXSIZE; //将 队头指针加1再取余MAXSIZE 的值赋给t
return Q->data[t]; //返回数组中下标为t的元素
}
}
void ShowQueue(SeqQueue* Q)//显示队中元素函数
{
int p = Q->front;
if (p == Q->rear)
printf("队列为空，无元素！\n");
else
{
printf("\n从队头起队列中的个元素为：");
while (p != Q->rear)
{
printf("%5d", Q->data[(p + 1) % MAXSIZE]);
p++;
p %= MAXSIZE; //使得p能从数组的首位地址重新遍历，形成循环，打印出所有的数组元素
}
}
}五、循环队列的函数使用
1.入队函数：InQueue
int main()
{
SeqQueue SQ;
InitQueue(&SQ);//初始化
InQueue(&SQ, 3);//入队
InQueue(&SQ, 4);//入队
InQueue(&SQ, 5);//入队
//插入3次，满了
InQueue(&SQ, 5);//第四次插入不了
ShowQueue(&SQ);//打印数组中所有的值
return 0;
}
结果：
插入3次，满了。第四次插入不了
2.取队头函数GetFront
int main()
{
SeqQueue SQ;
InitQueue(&SQ);//初始化
InQueue(&SQ, 3);//入队
InQueue(&SQ, 4);//入队
InQueue(&SQ, 5);//入队
//插入3次，满了
printf("循环队列中的元素依次是:");
ShowQueue(&SQ);//打印数组中所有的值
printf("\n");
DataType x = GetFront(&SQ);//取队头元素
printf("\n队头元素是：%d \n", x);
return 0;
}
结果：
3.出队函数DeQueue
int main()
{
SeqQueue SQ;
InitQueue(&SQ);//初始化
InQueue(&SQ, 3);//入队
InQueue(&SQ, 4);//入队
InQueue(&SQ, 5);//入队
//插入3次，满了
printf("循环队列中的元素依次是:");
ShowQueue(&SQ);//打印数组中所有的值
printf("\n\n");
DeQueue(&SQ);//出队一次
InQueue(&SQ,99);//出队之后，再入队一次
printf("操作后循环队列中的元素依次是:");
ShowQueue(&SQ);//打印数组中所有的值
return 0;
}结果；
出队之后，再入队一次，打印新的循环队列
六、心得体会
- 队列是一种运算受限制的线性表，插入在队尾，删除在队头。
- 队列的逻辑结构和线性表也相同，数据元素之间存在一对一的关系，它的主要特性是先进先出
- 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素。
- 由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear，分别知识队头元素和队尾元素在数组中的位置。
- 普通的顺序队列会有假溢出，一个巧妙的办法就是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。
