循环队列如何改写为长尾词的？

本文共计2707个文字，预计阅读时间需要11分钟。

为了避免当只有一个元素时，队首和队尾重合导致的处理混乱，引入两个指针+front+和+rear+。+front+即队首指针，指向队列头元素，+rear+即队尾指针，指向队列尾元素的下一个位置。这样，当进行队列操作时，只需要关注这两个指针的位置即可。

为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针front和rear。

front即队头指针指向队头元素，rear即队尾指针指向队尾元素的下一个元素。

这样当front等于rear是，不是队列中有一个元素，而是表示空队列。

假设数组长度为5，空队列即初始状态如图所示，front和rear都指向下标为0的位置。

当队列中有四个元素时，front不变，rear指向下标为4的位置。

若出队两个元素，front指向下标为2的位置，rear不变，再入队一个元素，front指针不变，但rear指针移动到数组之外。

假设该队列中数据元素总个数不超过5个，但是目前如果接着入队的话，会导致数组越界的问题。

但是队列在下标为0和1的位置是没有元素的。我们把这个现象叫做"假溢出"。

---

1. 概念

解决假溢出的办法就是后面满了，再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

此时如果再入列一个元素，会发现rear和front重合了。重合则无法判断其是满还是空。

解决办法：当队列空时，判断条件就是rear == front，当队列满时，我们修改其判断条件，保留一个元素空闲。也就说，当队列满时，数组中还有一个空闲单元。上面这种情况，我们认为队列已经满了。

为了使得满队和空队能够区分出来，必须牺牲一个数组单元，提前定义满队状态；

假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组。

此时一个满队的条件是rear加一，对循环队列长度取余后，等于front则说明其是满队。

(rear+1)%N == front

1. 逻辑结构：线性结构
2. 物理结构：顺序存储结构

2. 接口实现

2.1. 定义操作循环队列的结构体

1. 定长数组
2. 队头指针front
3. 队尾指针rear

// 1. 定义操作循环队列的结构体 #define N 10 typedef int DataType; typedef struct SeqQueue { DataType data[N]; int front; int rear; } SQ;

2.2. 创建空的循环队列

// 2. 创建一个空的队列 SQ *SQCreate() { // 2.1 开辟空间存放操作队列的结构体 SQ *PQ = (SQ *)malloc(sizeof(SQ)); if (NULL == PQ) { printf("SQCreate failed, PQ malloc err.\n"); return NULL; } // 2.2 初始化结构体成员 PQ->front = PQ->rear = 0; return PQ; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); return 0; }

2.3. 入列

1. 判满
2. 数据入列
3. 移动尾指针

// 3. 数据入列 void SQPush(SQ *PQ, DataType data) { // 3.1 容错判断——判满 if ((PQ->rear+1)%N == PQ->front) { printf("SQPush failed, SQ is full.\n"); return ; } // 3.2 数据入列 PQ->data[PQ->rear] = data; // 3.3 移动尾指针 PQ->rear = (PQ->rear + 1) % N; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); SQPush(PQ, 111); SQPush(PQ, 222); SQPush(PQ, 333); return 0; }

2.4. 出列

1. 容错判断——判空
2. 保存出列数据
3. 移动队头指针
4. 返回出列数据

// 4. 数据出列 DataType SQPop(SQ *PQ) { // 4.1 容错判断——判空 if (PQ->front == PQ->rear) { printf("SQPop failed, SQ is empty.\n"); return -1; } // 4.2 保存出列数据 DataType data = PQ->data[PQ->front]; // 4.3 移动队头指针 PQ->front = (PQ->front+1)%N; // 4.4 返回出列数据 return data; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); SQPush(PQ, 111); SQPush(PQ, 222); SQPush(PQ, 333); DataType data = SQPop(PQ); printf("SQPop data is %d\n", data); // SQPop data is 111 return 0; }

SQPop data is 111

2.5. 列长

// 5. 列长 int SQLength(SQ *PQ) { return (PQ->rear + N - PQ->front) % N; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); SQPush(PQ, 111); SQPush(PQ, 222); SQPush(PQ, 333); DataType data = SQPop(PQ); printf("SQPop data is %d\n", data); // SQPop data is 111 int len = SQLength(PQ); printf("SQLength is %d\n", len); // SQLength is 2 return 0; }

SQPop data is 111 SQLength is 2

2.6. 清空

// 6. 清空 void SQClear(SQ *PQ) { PQ->front = PQ->rear = 0; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); SQPush(PQ, 111); SQPush(PQ, 222); SQPush(PQ, 333); DataType data = SQPop(PQ); printf("SQPop data is %d\n", data); // SQPop data is 111 int len = SQLength(PQ); printf("SQLength is %d\n", len); // SQLength is 2 SQClear(PQ); len = SQLength(PQ); printf("SQLength is %d\n", len); // SQLength is 0 free(PQ); PQ = NULL; return 0; }

SQPop data is 111 SQLength is 2 SQLength is 0

2.7. 总结

#ifndef _SQ_H_ #define _SQ_H_ #include <stdio.h> #include <stdlib.h> // 1. 定义操作循环队列的结构体 #define N 10 typedef int DataType; typedef struct SeqQueue { DataType data[N]; int front; int rear; } SQ; // 2. 创建一个空的队列 SQ *SQCreate(); // 3. 数据入列 void SQPush(SQ *PQ, DataType data); // 4. 数据出列 DataType SQPop(SQ *PQ); // 5. 列长 int SQLength(SQ *PQ); // 6. 清空 void SQClear(SQ *PQ); #endif

#include "SQ.h" // 2. 创建一个空的队列 SQ *SQCreate() { // 2.1 开辟空间存放操作队列的结构体 SQ *PQ = (SQ *)malloc(sizeof(SQ)); if (NULL == PQ) { printf("SQCreate failed, PQ malloc err.\n"); return NULL; } // 2.2 初始化结构体成员 PQ->front = PQ->rear = 0; return PQ; } // 3. 数据入列 void SQPush(SQ *PQ, DataType data) { // 3.1 容错判断——判满 if ((PQ->rear+1)%N == PQ->front) { printf("SQPush failed, SQ is full.\n"); return ; } // 3.2 数据入列 PQ->data[PQ->rear] = data; // 3.3 移动尾指针 PQ->rear = (PQ->rear + 1) % N; } // 4. 数据出列 DataType SQPop(SQ *PQ) { // 4.1 容错判断——判空 if (PQ->front == PQ->rear) { printf("SQPop failed, SQ is empty.\n"); return -1; } // 4.2 保存出列数据 DataType data = PQ->data[PQ->front]; // 4.3 移动队头指针 PQ->front = (PQ->front+1)%N; // 4.4 返回出列数据 return data; } // 5. 列长 int SQLength(SQ *PQ) { return (PQ->rear + N - PQ->front) % N; } // 6. 清空 void SQClear(SQ *PQ) { PQ->front = PQ->rear = 0; }

#include "SQ.h" int main(int argc, char const *argv[]) { // 2. 创建空的循环队列 SQ *PQ = SQCreate(); SQPush(PQ, 111); SQPush(PQ, 222); SQPush(PQ, 333); DataType data = SQPop(PQ); printf("SQPop data is %d\n", data); // SQPop data is 111 int len = SQLength(PQ); printf("SQLength is %d\n", len); // SQLength is 2 SQClear(PQ); len = SQLength(PQ); printf("SQLength is %d\n", len); // SQLength is 0 free(PQ); PQ = NULL; return 0; }