线性表之队列详解

前言

队列（Queue）作为线性表的重要一员，以其独特的 “先进先出（First In First Out，FIFO）” 特性，从操作系统的任务调度到网络请求的处理，从广度优先搜索算法到消息队列系统，队列的身影随处可见。本文我将深入剖析队列的基本原理、实现方式、操作特性以及丰富的应用场景，结合具体的代码示例，帮助读者全面掌握这一重要的数据结构。

一、队列的基本概念

1.1 队列的定义与特性

队列是一种特殊的线性表，它只允许在表的一端进行插入操作（称为入队，enqueue），在另一端进行删除操作（称为出队，dequeue）。允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。这种操作方式使得最先进入队列的元素会最先被取出，就像日常生活中的排队一样，先排队的人先接受服务，体现了 “先进先出” 的特性。

队列的主要操作包括：

• 入队（Enqueue）：将元素添加到队尾。

• 出队（Dequeue）：从队头移除并返回元素。

• 查看队头元素（Peek）：返回队头元素但不移除它。

• 判断队列是否为空（Is Empty）：检查队列中是否没有元素。

• 获取队列大小（Size）：返回队列中元素的个数。

1.2 队列与其他线性表的区别

与数组和栈相比，队列的操作特性有明显差异：

• 数组：支持随机访问，可在任意位置插入和删除元素（但插入和删除操作平均时间复杂度较高），适用于需要快速定位元素的场景。

• 栈：遵循 “后进先出” 原则，操作集中在栈顶，常用于函数调用、表达式求值等场景。

• 队列：遵循 “先进先出” 原则，操作分别在队头和队尾进行，适用于需要按顺序处理元素的场景，如任务排队、消息处理等。

二、队列的实现方式

队列可以使用数组或链表来实现，不同的实现方式在性能和适用场景上各有优劣。

2.1 数组实现队列（顺序队列）

使用数组实现队列时，需要定义一个固定大小的数组来存储元素，并使用两个变量front和rear分别记录队头和队尾的位置。初始时，front和rear都指向数组的起始位置（通常为 0）。

#include <iostream>
using namespace std;const int MAX_SIZE = 100;class ArrayQueue {
private:int front, rear;int arr[MAX_SIZE];
public:ArrayQueue() {front = rear = -1;}// 判断队列是否为空bool isEmpty() {return front == -1;}// 判断队列是否已满bool isFull() {return (rear + 1) % MAX_SIZE == front;}// 入队操作void enqueue(int value) {if (isFull()) {cout << "队列已满，无法入队" << endl;return;}if (isEmpty()) {front = rear = 0;} else {rear = (rear + 1) % MAX_SIZE;}arr[rear] = value;}// 出队操作int dequeue() {if (isEmpty()) {cout << "队列已空，无法出队" << endl;return -1;}int value = arr[front];if (front == rear) {front = rear = -1;} else {front = (front + 1) % MAX_SIZE;}return value;}// 查看队头元素int peek() {if (isEmpty()) {cout << "队列已空" << endl;return -1;}return arr[front];}
};

上述代码中，为了避免数组实现队列时出现 假溢出现象（即数组中还有空闲位置，但rear已指向数组末尾）的情况，采用了循环队列的方式，通过取模运算（%）来实现队头和队尾指针的循环移动。

2.2 链表实现队列（链式队列）

使用链表实现队列时，每个节点包含数据域和指向下一个节点的指针。队头指针指向链表的第一个节点，队尾指针指向链表的最后一个节点。

#include <iostream>
using namespace std;// 定义链表节点结构
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};class ListQueue {
private:ListNode* front;ListNode* rear;
public:ListQueue() {front = rear = NULL;}// 判断队列是否为空bool isEmpty() {return front == NULL;}// 入队操作void enqueue(int value) {ListNode* newNode = new ListNode(value);if (isEmpty()) {front = rear = newNode;} else {rear->next = newNode;rear = newNode;}}// 出队操作int dequeue() {if (isEmpty()) {cout << "队列已空，无法出队" << endl;return -1;}int value = front->val;ListNode* temp = front;front = front->next;if (front == NULL) {rear = NULL;}delete temp;return value;}// 查看队头元素int peek() {if (isEmpty()) {cout << "队列已空" << endl;return -1;}return front->val;}
};

链表实现的队列无需担心队列满的问题，因为链表可以动态分配内存，但会有额外的指针空间开销。

三、队列的应用场景

3.1 任务调度

在操作系统中，任务调度器通常使用队列来管理待执行的任务。新产生的任务会被加入到任务队列的队尾，调度器按照一定的策略（如先来先服务、时间片轮转等）从队头取出任务进行执行，确保任务按照进入系统的顺序依次得到处理，维持系统的有序运行 。

3.2 广度优先搜索（BFS）

在图论算法中，广度优先搜索算法利用队列来存储待访问的节点。从起始节点开始，将其加入队列，然后不断从队列中取出节点进行访问，并将其未访问的邻接节点加入队列，直到队列为空。这种方式能够保证按照距离起始节点由近到远的顺序遍历图中的节点，常用于寻找最短路径、遍历迷宫等问题。

3.3 消息队列系统

在分布式系统和异步编程中，消息队列被广泛应用。生产者将消息发送到消息队列中（入队操作），消费者从消息队列中获取消息进行处理（出队操作）。消息队列可以实现生产者和消费者的解耦，提高系统的可扩展性和稳定性，同时保证消息按照发送的顺序被处理 。

3.4 打印机任务排队

在共享打印机的场景中，多个打印任务会形成一个队列。新提交的打印任务加入队列末尾，打印机按照队列顺序依次处理任务，避免了打印任务的混乱，确保每个任务都能得到公平处理。

四、队列的性能分析

实现方式	入队操作时间复杂度	出队操作时间复杂度	空间复杂度	优点	缺点
数组实现（循环队列）	$O(1)$	$O(1)$	$O(n)$（固定大小）	实现简单，访问速度快	大小固定，可能出现队列满的情况
链表实现	$O(1)$	$O(1)$	$O(n)$（动态）	无队列满限制，可动态扩展	有额外指针开销，内存不连续

总结

队列作为一种遵循 “先进先出” 原则的线性表数据结构，以其独特的操作特性和广泛的应用场景，成为数据结构线性表中不可或缺的一部分。无论是在系统底层的任务调度，还是在高层的算法设计与软件开发中，队列都发挥着重要作用。通过掌握队列的基本概念、实现方式以及应用场景，我们能够在实际编程中根据需求选择合适的队列实现方案，解决各种复杂的问题。

That’s all, thanks for reading!
创作不易，点赞鼓励；
知识无价，收藏备用；
持续精彩，关注不错过！