数据结构_循环队列_牺牲一个存储空间_不牺牲额外的存储空间 Circular Queue(C语言实现_超详细)

循环队列的引出

在前面我们学了基于顺序表的单向队列，这个形式的队列有个坏处，那就是比较浪费时间，例如：
在队列中：最大的容量为 5 ，那么在需要出队的时候，就需要将 索引为0 的元素删除，在顺序表中删除也就是意味着将这个顺序表整体向前移动一位，这个操作及其的浪费时间，所以，为了解决这个问题，诞生出了循环队列

区别普通队列和循环队列

下来举个例子，可以更加清晰的认识到普通队列和循环队列

例如：队列中已经存在 1 2 3 4 5 ，此时 head 指针位于 1 ,tail 指针由于指向下一个需要插入的位置，按道理来说，tail 应该位于 5 的下一位 ,也就是索引为 5 的位置，此时队列执行pop()操作，那么这个顺序表整体向前移动，变为 2 3 4 5 _ 此时，head 在 索引为 0 的位置，tail在索引为 4 的位置，要执行pop()操作，需要一个while()循环，所以时间复杂度为O(n)。

循环队列的话，原来 1 2 3 4 5 head 指向 索引 0 的位置，在循环队列中，tail指针仍然指向下一个插入位置（索引5），但通过模运算实现循环复用（因为要循环回去，对空间进行重复利用），执行pop()操作（执行pop()操作之后，val(1)虽然还在数组中，但已经被逻辑上删除，下次push()操作时会直接被覆盖），head = (head + 1) % capacity,此时head 指向索引为 1 的位置。

两种循环队列的概念

以上是基于没有牺牲一个额外空间的循环队列，循环队列是有两种实现的：

• 牺牲一个存储空间，来判断队列是否为满
  这种方式下，队列的实际可存储容量为 capacity - 1

  • 判断条件简单明了：

  • 空队列：head == tail

  • 满队列：(tail + 1) % capacity == head

  • 优点：实现简单，逻辑清晰

  • 缺点：浪费一个存储单元的空间-

• 不牺牲一个存储空间，这样就不能判断队列是否为满，这样就不能单纯通过head和tail的位置关系来判断队列是否为满，只可以通过引入额外的变量来实现完整的判断：

  • 使用计数器（count）记录当前队列中的元素个数

  • 空队列：count == 0

  • 满队列：count == capacity

  • 或者使用标志位（full）来标记队列状态

  • 空队列：head == tail && full == false

    • rear == front 且 count == 0 就表示队列为空

  • 满队列：head == tail && full == true

  • 优点：100%利用预分配的内存空间

  • 缺点：需要维护额外变量，逻辑相对复杂

• 两种实现方式的唯一本质区别就在于如何判断队列已满

  • 牺牲空间：用数学位置关系判断，无额外开销
  • 不牺牲空间：用计数器判断，需要维护count变量

下来通过一道题，来详细的解读一下循环队列

循环队列深入理解

题目：

描述：
循环队列存储空间 Q(0:5) （容量 = 6），初始状态 front = rear = 0,依次执行

1. 入队 A，B, C , D
2. 出队两次
3. 入队 E, F G , H
4. 出队一次
   求最终 front 和 rear 的值，并计算元素个数。

当front==rear时队列为空

此题，分为牺牲一个额外空间和不牺牲一个额外空间

不牺牲一个额外空间

完成第一步

front = 4 rear =0

count+=4;=4

完成第二步

front = 2 , rear = 4
count-=2;=2

完成第三步

rear= front = 2
此时队满，记录的count+=4=6 -> count == capacity
此时 rear == front == 2，但因为 count == 6 == capacity，所以队列已满

完成第四步

front =3 , rear =2
此时队中元素为：

（rear-front+capacity）% capacity=(2-3+6) % 6=5 正确

牺牲一个额外空间

完成第一步

front = 0 ,rear = 4

完成第二步

front =2 , rear =4

完成第三步

front = 2 ,rear =1
此时判断队列是否为满时 (rear+ 1 ) % capacity == front

虽然物理上还有一个空位（索引1），但按照牺牲一个空间的设计原则，(rear + 1) % capacity == front 时即认为队列已满

(1+1)%6 == 2; 所以判断队列为满

完成第四步

front =3 , rear =1

	情况(eare== front)
牺牲空间	一定是空队列
不牺牲空间	可能是空或满

代码实现循环队列

不牺牲额外空间

首先还是定义Queue和vector
因为是不牺牲额外的空间，所以必须要使用count来记录队列中现在的元素，capacity记录总容量

结构定义

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#define MAX_CAPACITY 5
typedef struct Vector {int* val;int capacity;//表示队列的容量
}vector;
typedef struct Queue {vector* data;//顺序表int front, rear, count;//分别代表队头，队尾，目前队列有多少个数;
}Queue;

初始化Queue 及 vector

vector* initVector() {vector *v=(vector *)malloc(sizeof(vector));if (v == NULL) {printf("error malloc vector\n");exit(-1);}v->capacity = MAX_CAPACITY;v->val = (int*)malloc(sizeof(int) * v->capacity);if (v->val == NULL) {printf("error malloc val\n");exit(-1);}return v;
}
Queue* initQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));if (q == NULL) {printf("error initQueue \n");exit(-1);}q->data = initVector();//获取顺序表q->count = q->front = q->rear = 0;//初始化队列各项数值return q;
}

释放内存：

void freeVector(vector* v) {free(v->val);free(v);return;
}
void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}

同样基于：

• empty：判断队列是否为空
• push：入队操作
• pop：出队操作
• Front：获取队头元素

empty()

当队列中现有的元素为0时，表示队列为空

bool empty(Queue* q) {return q->count == 0;
}

push()

如果队列为满，则输出提示信息，并返回-1 代表push失败

例如rear 在 push之前位于 4 这个位置(走到了顺序表的末尾)，那么
(4+1)%5=0,又回到了0号索引

int push(Queue * q, int val) {if (q->count == q->data->capacity) {printf("队列已满无法入队\n");return -1;}q->data->val[q->rear] = val;q->rear = (q->rear + 1) % q->data->capacity;//确认rear位置q->count++;return 1;
}

pop()

跟push同样的原理

int pop(Queue* q) {if (empty(q)) {printf("队列为空，无法出队\n");return -1;}int result = Front(q);q->front = (q->front + 1) % q->data->capacity;//获取最新front的位置q->count--;return 1;
}

Front()

int Front(Queue* q) {if (empty(q)) {printf("队列为空无法获取队头元素\n");return -1;}return q->data->val[q->front];
}

输出打印

如果为空队列，那么就输出提示信息，直接返回
如果直接使用q->front，由于是地址传递，会导致队列中的front 指向错误的位置，所以使用一个临时变量index来确保front的位置始终不变

void outAll(Queue * q) {if (empty(q)) {printf("Queue : NULL\n");return;}printf("Queue :");int index = q->front;for (int i = 0; i < q->count; i++) {printf("%3d ", q->data->val[index]);index = (index + 1) % q->data->capacity;}printf("\n");return;
}

测试

//测试代码
int main() {Queue* q = initQueue();srand(time(NULL));
#define MAX_OP 10for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0:	printf("将%3d pop出队列\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4:printf("将 %3d  push进队列\n", val);push(q, val);break;}outAll(q);}return 0;
}

完整代码(不牺牲额外空间)：

//不牺牲空间的循环队列
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#define MAX_CAPACITY 5
typedef struct Vector {int* val;int capacity;//表示队列的容量
}vector;
typedef struct Queue {vector* data;//顺序表int front, rear, count;//分别代表队头，队尾，目前队列有多少个数;
}Queue;vector* initVector() {vector *v=(vector *)malloc(sizeof(vector));if (v == NULL) {printf("error malloc vector\n");exit(-1);}v->capacity = MAX_CAPACITY;v->val = (int*)malloc(sizeof(int) * v->capacity);if (v->val == NULL) {printf("error malloc val\n");exit(-1);}return v;
}
Queue* initQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));if (q == NULL) {printf("error initQueue \n");exit(-1);}q->data = initVector();//获取顺序表q->count = q->front = q->rear = 0;//初始化队列各项数值return q;
}
bool empty(Queue* q) {return q->count == 0;
}
int push(Queue * q, int val) {if (q->count == q->data->capacity) {printf("队列已满无法入队\n");return -1;}q->data->val[q->rear] = val;q->rear = (q->rear + 1) % q->data->capacity;q->count++;return 1;
}
int Front(Queue* q) {if (empty(q)) {printf("队列为空无法获取队头元素\n");return -1;}return q->data->val[q->front];
}
int pop(Queue* q) {if (empty(q)) {printf("队列为空，无法出队\n");return -1;}int result = Front(q);q->front = (q->front + 1) % q->data->capacity;//获取最新front的位置q->count--;return result;//返回被弹出的元素}
void freeVector(vector* v) {free(v->val);free(v);return;
}
void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}
void outAll(Queue * q) {if (empty(q)) {printf("Queue : NULL\n");return;}printf("Queue :");int index = q->front;for (int i = 0; i < q->count; i++) {printf("%3d ", q->data->val[index]);index = (index + 1) % q->data->capacity;}printf("\n");return;
}
//测试代码
int main() {Queue* q = initQueue();srand(time(NULL));
#define MAX_OP 10for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0:	printf("将%3d pop出队列\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4:printf("将 %3d  push进队列\n", val);push(q, val);break;}outAll(q);}return 0;
}

牺牲额外空间

相较于不牺牲一个空间，牺牲空间只可以存储4个元素

结构定义

定义时缺少了count变量

//牺牲一个空间的循环队列
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#define MAX_CAPACITY 5
typedef struct Vector {int* val;int capacity;//表示队列的容量
}vector;
typedef struct Queue {vector* data;//顺序表int front, rear;//分别代表队头，队尾
}Queue;

初始化Queue 及 vector

vector* initVector() {vector *v=(vector *)malloc(sizeof(vector));if (v == NULL) {printf("error malloc vector\n");exit(-1);}v->capacity = MAX_CAPACITY;v->val = (int*)malloc(sizeof(int) * v->capacity);if (v->val == NULL) {printf("error malloc val\n");exit(-1);}return v;
}
Queue* initQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));if (q == NULL) {printf("error initQueue \n");exit(-1);}q->data = initVector();//获取顺序表q->front = q->rear = 0;//初始化队列各项数值return q;
}

释放内存

void freeVector(vector* v) {free(v->val);free(v);return;
}
void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}

empty()

牺牲一个空间为空的条件是 q->front == q->rear

bool empty(Queue* q) {return  q->front == q->rear;
}

push()

int push(Queue * q, int val) {if ((q->rear+1)%q->data->capacity ==q->front) {printf("队列已满无法入队\n");return -1;}q->data->val[q->rear] = val;q->rear = (q->rear + 1) % q->data->capacity;return 1;
}

pop()

int pop(Queue* q) {if (empty(q)) {printf("队列为空，无法出队\n");return -1;}q->front = (q->front + 1) % q->data->capacity;//获取最新front的位置return 1;}

Front()

int Front(Queue* q) {if (empty(q)) {printf("队列为空无法获取队头元素\n");return -1;}return q->data->val[q->front];
}

输出打印

通过公式：(rear-front+capacity)%capacity计算出当前队列有多少个元素

void outAll(Queue * q) {if (empty(q)) {printf("Queue : NULL\n");return;}printf("Queue :");int index = q->front;int count=(q->rear-q->front+q->data->capacity)%q->data->capacity;for (int i = 0; i < count; i++) {printf("%3d ", q->data->val[index]);index = (index + 1) % q->data->capacity;}printf("\n");return;
}

测试

//测试代码
int main() {Queue* q = initQueue();srand(time(NULL));
#define MAX_OP 15for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0:	printf("将%3d pop出队列\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4:printf("将 %3d  push进队列\n", val);push(q, val);break;}outAll(q);}return 0;
}

完整代码（牺牲一个存储空间）

//牺牲一个空间的循环队列
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#define MAX_CAPACITY 5
typedef struct Vector {int* val;int capacity;//表示队列的容量
}vector;
typedef struct Queue {vector* data;//顺序表int front, rear;//分别代表队头，队尾
}Queue;vector* initVector() {vector *v=(vector *)malloc(sizeof(vector));if (v == NULL) {printf("error malloc vector\n");exit(-1);}v->capacity = MAX_CAPACITY;v->val = (int*)malloc(sizeof(int) * v->capacity);if (v->val == NULL) {printf("error malloc val\n");exit(-1);}return v;
}
Queue* initQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));if (q == NULL) {printf("error initQueue \n");exit(-1);}q->data = initVector();//获取顺序表q->front = q->rear = 0;//初始化队列各项数值return q;
}
bool empty(Queue* q) {return  q->front == q->rear;
}
int push(Queue * q, int val) {if ((q->rear+1)%q->data->capacity ==q->front) {printf("队列已满无法入队\n");return -1;}q->data->val[q->rear] = val;q->rear = (q->rear + 1) % q->data->capacity;return 1;
}
int Front(Queue* q) {if (empty(q)) {printf("队列为空无法获取队头元素\n");return -1;}return q->data->val[q->front];
}
int pop(Queue* q) {if (empty(q)) {printf("队列为空，无法出队\n");return -1;}q->front = (q->front + 1) % q->data->capacity;//获取最新front的位置return 1;}
void freeVector(vector* v) {free(v->val);free(v);return;
}
void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}
void outAll(Queue * q) {if (empty(q)) {printf("Queue : NULL\n");return;}printf("Queue :");int index = q->front;int count=(q->rear-q->front+q->data->capacity)%q->data->capacity;for (int i = 0; i < count; i++) {printf("%3d ", q->data->val[index]);index = (index + 1) % q->data->capacity;}printf("\n");return;
}
//测试代码
int main() {Queue* q = initQueue();srand(time(NULL));
#define MAX_OP 15for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0:	printf("将%3d pop出队列\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4:printf("将 %3d  push进队列\n", val);push(q, val);break;}outAll(q);}return 0;
}