当前位置：首页 > news >正文

【数据结构】队列：定义、顺序队列与链式队列

news 2026/8/21 3:23:44

考点频率：★★★★★（数据结构必考，选择题常考循环队列的判空/判满条件）
难度：⭐⭐⭐
建议：重点理解队列的FIFO特性，掌握循环队列中front和rear指针的含义，以及判空、判满的条件判断

1️⃣ 什么是队列？

队列（Queue）是一种操作受限的线性表。它的核心特征是：只允许在表的一端进行插入，在另一端进行删除。

队尾（Rear）：允许插入的一端
队头（Front）：允许删除的一端

核心特性：先进先出（FIFO，First In First Out）——最先进入队列的元素，最先被移出。

打个比方：队列就像食堂打饭的排队。新来的人站在队伍末尾（入队），队伍最前面的人打完饭离开（出队）。先来的人先打饭，后来的人后打饭——这就是FIFO。

队列在计算机系统里非常常见：CPU的进程调度、打印机任务队列、键盘缓冲区……都是队列的应用。

2️⃣ 队列的基本操作

操作	含义	时间复杂度
入队（Enqueue）	将元素插入到队尾	O(1)O(1)O(1)
出队（Dequeue）	移除队头元素并返回	O(1)O(1)O(1)
取队头（Front / Peek）	查看队头元素但不移除	O(1)O(1)O(1)
判空（IsEmpty）	检查队列是否为空	O(1)O(1)O(1)
判满（IsFull）	检查队列是否已满（顺序队列）	O(1)O(1)O(1)

3️⃣ 顺序队列（数组实现）

3.1 普通顺序队列的“假溢出”问题

用数组实现队列时，我们使用两个指针：

front：指向队头元素
rear：指向队尾元素的下一个位置

#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intfront;// 队头指针intrear;// 队尾指针（指向下一个空闲位置）}SeqQueue;

入队操作：data[rear] = 元素; rear++
出队操作：元素 = data[front]; front++

问题：随着入队和出队的进行，front和rear都在不断向后移动。当rear == MAXSIZE时，即使数组前面还有空闲位置（因为出队释放了空间），也无法再入队了。这就是假溢出。

3.2 循环队列（解决假溢出）

核心思想：把数组想象成一个首尾相连的环。当rear到达数组末尾时，下一步就绕回到数组开头。

关键约定（软考必考）：

约定项	说明
`front`	指向队头元素的位置
`rear`	指向队尾元素的下一个位置
判空	`front == rear`
判满	`(rear + 1) % MAXSIZE == front`
元素个数	`(rear - front + MAXSIZE) % MAXSIZE`

⚠️注意：循环队列中，为了区分“空”和“满”，我们牺牲一个存储单元——当(rear+1) % MAXSIZE == front时判满，此时实际上还有一个空位没有放数据。

入队操作：

if((rear+1)%MAXSIZE==front){// 队列已满，报错}data[rear]=元素;rear=(rear+1)%MAXSIZE;

出队操作：

if(front==rear){// 队列为空，报错}元素=data[front];front=(front+1)%MAXSIZE;

为什么牺牲一个空间？
因为我们无法区分front == rear到底代表“队列为空”还是“队列为满”。如果不牺牲这个空间，两种状态的条件就会完全一样。牺牲一个空间后，“满”的条件变成了(rear+1)%MAXSIZE == front，和“空”的条件front == rear区分开了。

4️⃣ 链式队列（链表实现）

4.1 核心结构

链式队列用单链表实现，队头是链表的头节点，队尾是链表的尾节点。

// 队列节点typedefstructQNode{intdata;structQNode*next;}QNode;// 链式队列（记录队头和队尾指针）typedefstruct{QNode*front;// 队头指针QNode*rear;// 队尾指针}LinkQueue;

4.2 基本操作

入队（在队尾插入新节点）：

QNode*newNode=(QNode*)malloc(sizeof(QNode));newNode->data=元素;newNode->next=NULL;if(rear==NULL){// 队列为空front=rear=newNode;}else{rear->next=newNode;rear=newNode;}

出队（移除队头节点）：

if(front==NULL){// 队列为空}QNode*temp=front;元素=temp->data;front=front->next;if(front==NULL){rear=NULL;// 队列变空}free(temp);

4.3 链式队列的优缺点

优点	缺点
容量动态增长，无假溢出问题	每个节点需要额外的指针空间
不需要预先分配连续空间	存储密度低

5️⃣ 循环队列 vs 链式队列（对比表）

对比项	循环队列（顺序）	链式队列
底层结构	数组	单链表
容量	固定（需预先分配）	动态增长
假溢出问题	通过循环解决	不存在
判空条件	`front == rear`	`front == NULL`
判满条件	`(rear+1) % MAXSIZE == front`	无（受内存限制）
存储密度	高	低
适用场景	元素个数可预知	元素个数不可预知