别再被队列 “假溢出” 坑了！循环队列这样学才高效

用户11957406

发布于 2025-12-24 10:16:51

2400

前言：

情景展现：以"公交车厢"为示例，假设车厢内设有8个固定座位（对应普通队列的8个内存空间），其运作规则与队列完全一致。

①乘客只能从后门（队尾）上车。

②乘客必须从前门（队头）下车。

③乘客下车后，座位不会自动前移填补空位

请思考，为什么在车厢中会出现假溢出，以及如何解决假溢出问题？

一、队列假溢出

1.1 假溢出拆解：从日常场景看懂它的本质

为了回答前言中的思考题，我们逐步来拆解假溢出，一步步看 “假溢出” 是怎么发生的：

1.第一步：坐满车厢

假设先上来 8 个人，分别坐在 1-8 号座位，此时 “队伍满了”（普通队列判断 “队满”），再有人想上车，系统会提示 “没位置了”，这是个很正常情况。

2.第二步：前排有人下车

坐 1、2、3 号座位的人到站下车，此时 1-3 号座位空了，但因为规则限制，4-8 号座位的人不能往前挪（普通队列的队头指针只会往后移，不会 “回头” 用前面的空位置）

3.第三步：新乘客上车被拒

这时候来了 2 个新乘客，想坐 1、2 号空座位，但系统一看 “队尾已经到 8 号了”（普通队列的队尾指针指向 8），还是提示 “没位置了”。明明有 2 个空座位，却没法用 —— 这就是普通队列的 “假溢出”，不是真的没空间，而是 “前面的空位置被浪费了”。

小结：正是因为普通队列中的 “队头指针” 和 “队尾指针” 只会单向移动，而队尾到了内存的 “末尾”，哪怕队头前面有大片空内存，也会被判定为 “队满”，这就是假溢出的本质。

1.2 假溢出的实际坑点：那些让我们卡壳的麻烦

麻烦 1：内存空间被 “隐形浪费”：

普通队列的内存一般是 “一次性分配” 的，比如你给队列分配了能存 100 条数据的空间，想用来存用户的操作日志。

但如果日志存满 100 条后，又删除了 50 条（队头前移 50 位），此时队列里实际只有 50 条数据，但因为假溢出，新的日志还是存不进来 —— 相当于 50% 的内存白分配了，只能频繁手动 “扩容”，既浪费资源，又会拖慢程序速度。

麻烦2：出现 “诡异 bug”，排查半天找不到原因

当我们遇到 “存不进数据” 时，第一反应往往是 “我是不是把队列容量设小了？” “是不是判断队满的代码写错了？”。

比如有个同学做 “消息队列” 功能，明明队列里只存了 30 条消息（容量 100），却死活存不进新消息，反复检查 “队满判断代码”，发现逻辑没问题，最后才意识到是假溢出 —— 这一来一回，可能半天时间就耗在上面了。

1.3 假溢出的空间浪费：用数据看明白浪费有多严重

从表格能明显看出：普通队列的 “可用空间” 会随着 “出队次数” 减少，这样导致空间利用率极其低下。

场景	普通队列（假溢出影响）
初始容量	100 个空间
入队 100 条数据	空间占满（利用率 100%）
出队 50 条数据（队头空 50 个）	剩余可用空间 0（利用率 50%）
再入队 30 条数据	无法存入（假溢出）
最终实际存储量	50 条（浪费 50 个空间）

二、循环队列

2.1 循环队列出现的起因

如何解决普通队列因为出队的操作，导致队列前部分的空间被浪费呢？

-其实本质上是要解决队头指针和队尾指针只能单向移动，一旦队尾指针走到了尾部，哪怕前面通过出队腾出了大块的空间也无法进行入队操作。

-基于这个痛点，我们通过设计循环队列就能很好的解决，即使队尾指针走到了尾部，因为循环队列逻辑结构上是环形的，所以队尾指针又会从起点开始，充分利用了前面出队腾出的大块空间，这也正是我们设计循环队列的原因。

2.2循环队列的设计

循环队列通过 “逻辑上让数组首尾相连”，直接破解 “假溢出” 问题：

1.入队时，若rear到达数组末尾，判断队头是否有空位，有空位则让rear绕回数组开头（而非直接判定满队）。

2.出队时，front向后移动，当front到达数组末尾，同样绕回开头，继续利用空闲空间。

这种 “循环复用” 的设计，彻底解决了普通队列空间浪费的问题，这也是循环队列存在的核心价值。

如图所示：在逻辑结构上循环队列是环形的。

如图所示：在物理结构上循环队列是基于数组实现的，若rear到达数组末尾，进入下一个循环。

2.3循环队列实现的相关接口

2.4循环队列实现的相关文件

2.5CircularQueue.h

CircularQueue.h头文件实现：通过结构体定义循环队列，声明循环队列的相关接口函数

#pragma once

#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>

typedef int CQDatatype;
	
typedef struct CircularQueue
{
	// 存储元素的数组
	CQDatatype* data; 
	
	//指向队头
	int front;

	//指向队尾
	int rear;

	//队列实际容量
	int capacity;

}CircularQueue;


//初始化队列
void QueueInit(CircularQueue* cq,int capacity);


//判断队列是否为空
bool isEmpty(CircularQueue* cq);


//判断队列是否为满
bool isFull(CircularQueue* cq);


//入队
bool enQueue(CircularQueue* cq, CQDatatype x);


//出队
bool deQueue(CircularQueue* cq);


//获取队头元素
CQDatatype getFront(CircularQueue* cq);


//获取队尾元素
CQDatatype getBack(CircularQueue* cq);


//销毁队列
void QueueDestroy(CircularQueue* cq);

对于CircularQueue.h主要关注如下代码：

代码1：

typedef int CQDatatype;
	
typedef struct CircularQueue
{
	// 存储元素的数组
	CQDatatype* data; 
	
	//指向队头
	int front;

	//指向队尾
	int rear;

	//队列实际容量
	int capacity;

}CircularQueue;

struct CircularQueue 创建循环队列的结构体 1.成员1为：CQDatatype* data -存储元素的数组 2.成员2为：int front; -指向队头（存储队头指向的下标） 3.成员3为：int rear; -指向队尾（存储队尾指向的下标） 4.成员4为：int capacity; -循环队列的容量 通过typedef int CQDatatype 方便以后进行修改存储在循环队列中的元素类型。

代码2：

//判断队列是否为空
bool isEmpty(CircularQueue* cq);


//判断队列是否为满
bool isFull(CircularQueue* cq);

如何判断循环队列为空呢？

如图所示：当队列为空时，队头指针和队尾指针都指向同一个位置，所以用rear==head来判断。

如何判断队列为满呢？

如图所示：当队列为满时，此时队尾指针进入下一个循环，即重新回到下标为0处。此时我们发现队列为满的条件仍然是：rear==head。

这样就导致了一个问题当head（头节点指针）==rear（尾节点指针）时，循环队列究竟是为满，还是为空呢，导致判断条件有了争议，逻辑出现了混乱。那么我们如何解决这个问题呢？ 一般有两个思路： 思路一：定义一个计数器size，根据size是否为0或则size是否为队列的总容量来进行判断，这样就避免了这个问题。 思路二：浪费一个空间。 此时当队列为空时：head==rear。 此时当队列为满时：队尾指针的下一个位置是队头指针。

我们以思路二为例：演示一下循环队列为空时的判断条件，循环队列为满时的判断条件。 假设队列的总容量为k=6，实际我们多开辟一个空间使得队列的总容量为k+1=7。

如图一所示：我们开辟k+1=7个空间，但循环队列可用空间为k=6，因为我们需要进行浪费一个空间，用于区别队满和队空的条件。

如图二所示：我们向循环队列中push6个元素分别为：1 2 3 4 5 6，此时循环队列为满，因为我们浪费了一个空间，实际可用空间为6，

队满的判断条件为：( rear + 1 ) % ( k + 1 )==head

如图三所示：我们向循环队列中pop6个元素，此时队列为空.

队满的判断条件为：rear==head。

如图四所示：我们向循环队列中push6个元素分别为：1 2 3 4 5 6，此时循环队列为满，因为我们浪费了一个空间，实际可用空间为6。

队满的判断条件为：rear+1==head <==> ( rear + 1 ) % ( k + 1 )==head

综上所述：通过多开辟一个空间的方式，能够区分队列为空的判定条件和队列为满的判定条件。 队列为满时：（rear+1）%（k+1）== head 队列为空时： rear==head

2.6CircularQueue.c

①循环队列的初始化

void QueueInit(CircularQueue* cq,int capacity)
{
	assert(cq);
	//初始化大小为100的空间
	cq->capacity = capacity;

	//预留一个空间
	cq->data = (CQDatatype *)malloc(sizeof(CQDatatype) * (cq->capacity +1 ) );
	if (cq->data == NULL)
	{
		perror("malloc fail");
		return;
	}
	cq->front = cq->rear = 0;
}

这里采用第二种方式：多开辟一个空间进行浪费的方式，规避队列和队满的判断条件相同。

②循环队列判断是否为空

//判断队列是否为空
bool isEmpty(CircularQueue* cq)
{
	assert(cq);
	return cq->front == cq->rear;
}

队列为空时：队头指针和队尾指针指向同一个位置。

③判断队列是否为满

//判断队列是否为满
bool isFull(CircularQueue* cq)
{
    assert(cq);
    return (cq->rear + 1) % (cq->capacity + 1)==cq->front ;
}

队列为满时：队尾指针的下一个位置是队头指针

④入队

//入队
bool enQueue(CircularQueue* cq, CQDatatype x)
{
	assert(cq);
	if (isFull(cq))
	{
		return false;
	}

	//进行入队操作
	cq->data[cq->rear] = x;

	//更新队尾指针指向
	cq->rear = (cq->rear + 1) % (cq->capacity + 1);
	return true;
}

温馨提示： ①：因为rear指针指向的是队尾元素的下一个位置，所以cq->data[cq->rear]就可以正确找到要插入的元素的下标， 如图所示：初始时rear指针和head指针都指向下标为0的位置，所以此时入队只需要cq->data[cq->rear] = x;

②：这里更新队尾指针指向的时候：cq->rear = (cq->rear + 1) % (cq->capacity + 1); 因为是循环队列的原因，所以队尾指针更新需要进行取模运算，使得队尾指针在循环队列中进行循环，而不是进行单向向后。

⑤出队

//出队
bool deQueue(CircularQueue* cq)
{
	assert(cq);
	if (isEmpty(cq))
	{
		return false;
	}

	//进行出队操作
	cq->front = (cq->front + 1) % (cq->capacity + 1);
	return true;
}

温馨提示： 这里更新队头指针指向的时候：cq->front = (cq->front + 1) % (cq->capacity + 1); 因为是循环队列的原因，所以队头指针更新需要进行取模运算，使得队头指针在循环队列中进行循环，而不是进行单向向后。

⑥获取队头元素

//获取队头元素
CQDatatype getFront(CircularQueue* cq)
{
	assert(cq);
	//队列为空时触发
	assert(!isEmpty(cq));

	return cq->data[cq->front];
}

温馨提示： 因为队头指向的就是队头元素，所以直接通过索引就可以返回队头元素。

⑦获取队尾元素

//获取队尾元素
CQDatatype getBack(CircularQueue* cq)
{
	assert(cq);
	assert(!isEmpty(cq));
	return cq->rear==0? cq->data[cq->capacity] : cq->data[cq->rear-1] ;
}

温馨提示： ①因为队尾指针，指向的是队尾元素的下一个位置，所以其索引cq->rear并不是队尾元素，其索引上一个下标位置cq->rear-1才是队尾元素。 ②如图所示：对于一般情况而言cq->rear-1是队尾元素，

③如图所示：对于特殊情况，rear指向下标为0的位置时，此时队尾元素的下标不再是rear-1，队尾元素的下标为：rear->capacity，其中capacity为空间可用空间容量。

⑧销毁队列

//销毁队列
void QueueDestroy(CircularQueue* cq)
{
	assert(cq);

	free(cq->data);
	cq->data = NULL;

	cq->capacity = cq->front = cq->rear = 0;
}

2.7Test.c

#include"CircularQueue.h"
#include<stdio.h>

// 原基础测试
void TestBasic()
{
    printf("=====基础功能测试=====\n");
    CircularQueue q1 = { 0 };

    QueueInit(&q1, 100);

    enQueue(&q1, 1);
    printf("入队1后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    enQueue(&q1, 2);
    printf("入队2后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    enQueue(&q1, 3);
    printf("入队3后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    enQueue(&q1, 4);
    printf("入队4后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));


    deQueue(&q1);
    printf("出队1次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    deQueue(&q1);
    printf("出队2次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    deQueue(&q1);
    printf("出队3次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1));
    deQueue(&q1);
    printf("出队4次后，队列是否为空：%s\n\n", isEmpty(&q1) ? "是" : "否");

    QueueDestroy(&q1);
}

// 测试队列满的情况
void TestFullQueue()
{
    printf("=====队列满测试=====\n");
    CircularQueue q;
    QueueInit(&q, 3);  // 实际可存储3个元素（预留1个空间）

    printf("入队1：%s\n", enQueue(&q, 1) ? "成功" : "失败");
    printf("入队2：%s\n", enQueue(&q, 2) ? "成功" : "失败");
    printf("入队3：%s\n", enQueue(&q, 3) ? "成功" : "失败");
    printf("队列是否已满：%s\n", isFull(&q) ? "是" : "否");

    // 尝试入队第4个元素（应失败）
    printf("入队4：%s\n", enQueue(&q, 4) ? "成功" : "失败");
    printf("当前队头：%d，队尾：%d\n\n", getFront(&q), getBack(&q));

    QueueDestroy(&q);
}

// 混合入队出队测试
void TestMixedOperation()
{
    printf("=====混合入队出队测试=====\n");
    CircularQueue q;
    QueueInit(&q, 5);

    enQueue(&q, 10);
    enQueue(&q, 20);
    printf("入队10、20后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));

    deQueue(&q);
    printf("出队1次后，队头：%d\n", getFront(&q));

    enQueue(&q, 30);
    enQueue(&q, 40);
    printf("入队30、40后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));

    deQueue(&q);
    deQueue(&q);
    printf("出队2次后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));

    enQueue(&q, 50);
    enQueue(&q, 60);
    enQueue(&q, 70);
    printf("入队50、60、70后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));
    printf("队列是否已满：%s\n\n", isFull(&q) ? "是" : "否");

    QueueDestroy(&q);
}

// 空队列操作测试
void TestEmptyQueue()
{
    printf("=====空队列操作测试=====\n");
    CircularQueue q;
    QueueInit(&q, 2);

    printf("初始队列是否为空：%s\n", isEmpty(&q) ? "是" : "否");
    printf("尝试出队（空队列）：%s\n", deQueue(&q) ? "成功" : "失败");

    // 注意：以下两行会触发assert（空队列不能获取元素）
    // printf("尝试获取队头：%d\n", getFront(&q));
    // printf("尝试获取队尾：%d\n", getBack(&q));

    enQueue(&q, 100);
    printf("入队100后，是否为空：%s\n\n", isEmpty(&q) ? "是" : "否");

    QueueDestroy(&q);
}

// 循环边界测试（队尾绕回起点）
void TestCircularBoundary()
{
    printf("=====循环边界测试=====\n");
    CircularQueue q;
    QueueInit(&q, 2);  // 实际可存2个元素

    enQueue(&q, 100);
    enQueue(&q, 200);
    printf("入队100、200后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));

    deQueue(&q);
    printf("出队1次后，队头：%d\n", getFront(&q));

    enQueue(&q, 300);  // 队尾会绕回数组起点
    printf("入队300后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q));
    printf("队列是否已满：%s\n", isFull(&q) ? "是" : "否");

    deQueue(&q);
    deQueue(&q);
    printf("出队2次后，是否为空：%s\n", isEmpty(&q) ? "是" : "否");

    enQueue(&q, 400);
    printf("入队400后，队头：%d，队尾：%d\n\n", getFront(&q), getBack(&q));

    QueueDestroy(&q);
}

int main()
{
    TestBasic();
    TestFullQueue();
    TestMixedOperation();
    TestEmptyQueue();
    TestCircularBoundary();
    return 0;
}