【数据结构】队列（Queue）详解——数据结构的“先进先出”
在学习数据结构的过程中，**队列（Queue）是继栈之后非常重要的一个结构。队列遵循先进先出（FIFO）**的原则，常常用于任务调度、消息处理等场景。今天我们将一起深入了解队列的基本概念、常见类型（普通队列、循环队列、链式队列）以及它们的实现方法。
一、什么是队列？
队列（Queue）是一种线性数据结构 ，它的特点是先进先出（FIFO） 。
队列的元素总是从队头（front）移除，而从队尾（rear）插入。你可以把队列想象成排队买票，最先排队的人最先买到票。
🧩 队列的形象比喻
假设你和朋友们排队买冰淇淋。你站在队伍的队尾，大家按照顺序排队，队伍中的每个人依次向前，直到最先排队的人先买到冰淇淋。你是队列中的一个元素，等待自己的回合。
队头（front）：最先排队的人。
队尾（rear）：最后排队的人。
队列操作简介
入队（Enqueue）：向队列的队尾插入元素。
出队（Dequeue）：从队列的队头移除元素。
队头元素（Front）：获取队头元素，但不移除。
队列是否为空（isEmpty）：检查队列是否为空。
队列是否满（isFull）：检查队列是否已满（仅对固定大小的队列有用）。
二、普通队列
📦 普通队列的定义
普通队列 是最基础的队列类型。它使用一个数组 来存储队列的元素，通过两个指针（front 和 rear）来表示队头和队尾的位置。
🌿 普通队列的实现（C++）
cpp
复制代码
#include
using namespace std;
#define MAX_SIZE 5 // 队列最大容量
class Queue {
private:
int arr[MAX_SIZE]; // 队列存储元素的数组
int front; // 队头指针
int rear; // 队尾指针
public:
Queue() {
front = -1; // 初始化队头为-1，表示队列为空
rear = -1; // 初始化队尾为-1
}
// 入队操作
void enqueue(int value) {
if (rear == MAX_SIZE - 1) {
cout << "队列已满，无法入队！" << endl;
return;
}
if (front == -1) front = 0; // 如果队列为空，设置队头为0
arr[++rear] = value; // 队尾指针向后移动，插入元素
cout << "入队：" << value << endl;
}
// 出队操作
void dequeue() {
if (front == -1 || front > rear) {
cout << "队列为空，无法出队！" << endl;
return;
}
cout << "出队：" << arr[front++] << endl; // 队头指针向后移动，移除元素
}
// 获取队头元素
int frontElement() {
if (front == -1 || front > rear) {
cout << "队列为空！" << endl;
return -1;
}
return arr[front]; // 返回队头元素
}
// 检查队列是否为空
bool isEmpty() {
return front == -1 || front > rear;
}
// 打印队列内容
void print() {
if (front == -1 || front > rear) {
cout << "队列为空！" << endl;
return;
}
cout << "队列内容：";
for (int i = front; i <= rear; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
💻 使用普通队列的演示（C++ 示例）
cpp
复制代码
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.print(); // 输出队列内容
q.dequeue(); // 出队
q.dequeue(); // 出队
q.print(); // 输出队列内容
cout << "队头元素：" << q.frontElement() << endl;
return 0;
}
🧑💻 代码输出：
复制代码
入队：10
入队：20
入队：30
入队：40
入队：50
队列内容：10 20 30 40 50
出队：10
出队：20
队列内容：30 40 50
队头元素：30
三、循环队列
📦 循环队列的定义
循环队列 是对普通队列的一种改进。普通队列存在一个问题，当队列的元素被移除后，虽然队列的空间被释放了，但是队头指针和队尾指针 可能会一直保持在队列的开头部分，这就导致了空间浪费。
为了避免这个问题，循环队列通过将队尾指针和队头指针做循环利用，实现队列的循环存储。换句话说，当队尾指针到达数组的末尾时，它会重新回到数组的开头。
🌿 循环队列的实现（C++）
cpp
复制代码
#include
using namespace std;
#define MAX_SIZE 5 // 队列最大容量
class CircularQueue {
private:
int arr[MAX_SIZE]; // 队列存储元素的数组
int front; // 队头指针
int rear; // 队尾指针
public:
CircularQueue() {
front = rear = -1; // 初始化队列为空
}
// 入队操作
void enqueue(int value) {
if ((rear + 1) % MAX_SIZE == front) { // 队列已满
cout << "队列已满，无法入队！" << endl;
return;
}
if (front == -1) front = 0; // 如果队列为空，设置队头为0
rear = (rear + 1) % MAX_SIZE; // 循环队尾指针
arr[rear] = value; // 插入元素
cout << "入队：" << value << endl;
}
// 出队操作
void dequeue() {
if (front == -1) {
cout << "队列为空，无法出队！" << endl;
return;
}
cout << "出队：" << arr[front] << endl;
if (front == rear) { // 队列只有一个元素
front = rear = -1;
} else {
front = (front + 1) % MAX_SIZE; // 循环队头指针
}
}
// 获取队头元素
int frontElement() {
if (front == -1) {
cout << "队列为空！" << endl;
return -1;
}
return arr[front]; // 返回队头元素
}
// 检查队列是否为空
bool isEmpty() {
return front == -1;
}
// 打印队列内容
void print() {
if (front == -1) {
cout << "队列为空！" << endl;
return;
}
cout << "队列内容：";
int i = front;
while (i != rear) {
cout << arr[i] << " ";
i = (i + 1) % MAX_SIZE; // 循环遍历
}
cout << arr[rear] << endl; // 打印队尾元素
}
};
💻 使用循环队列的演示（C++ 示例）
cpp
复制代码
int main() {
CircularQueue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.print(); // 输出队列内容
q.dequeue(); // 出队
q.dequeue(); // 出队
q.print(); // 输出队列内容
cout << "队
头元素：" << q.frontElement() << endl;
复制代码
return 0;
}
复制代码
### 🧑💻 代码输出：
入队：10
入队：20
入队：30
入队：40
入队：50
队列内容：10 20 30 40 50
出队：10
出队：20
队列内容：30 40 50
队头元素：30
复制代码
---
## 四、链式队列
### 📦 链式队列的定义
**链式队列**使用**链表**来实现队列。在链式队列中，每个元素（节点）不仅包含数据，还包含指向下一个元素的指针。链式队列的优点是可以动态地扩展，不会受到固定容量的限制。
### 🌿 链式队列的实现（C++）
```cpp
#include
using namespace std;
struct Node {
int data;
Node* next;
};
class LinkedQueue {
private:
Node* front; // 队头指针
Node* rear; // 队尾指针
public:
LinkedQueue() {
front = rear = nullptr; // 初始化队列为空
}
// 入队操作
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (rear == nullptr) {
front = rear = newNode; // 如果队列为空，头尾指针都指向新节点
} else {
rear->next = newNode; // 将新节点加入队尾
rear = newNode;
}
cout << "入队：" << value << endl;
}
// 出队操作
void dequeue() {
if (front == nullptr) {
cout << "队列为空，无法出队！" << endl;
return;
}
Node* temp = front;
cout << "出队：" << temp->data << endl;
front = front->next; // 队头指针后移
delete temp; // 释放内存
}
// 获取队头元素
int frontElement() {
if (front == nullptr) {
cout << "队列为空！" << endl;
return -1;
}
return front->data; // 返回队头元素
}
// 检查队列是否为空
bool isEmpty() {
return front == nullptr;
}
// 打印队列内容
void print() {
if (front == nullptr) {
cout << "队列为空！" << endl;
return;
}
cout << "队列内容：";
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
五、小结
队列类型
特点
优点
缺点
普通队列
使用数组实现，队头和队尾使用指针管理
实现简单，适用于固定大小的队列
队列满时无法扩展，空间利用率低
循环队列
对普通队列的优化，通过循环利用数组空间
更高效的空间利用
需要处理队头和队尾指针的循环问题
链式队列
使用链表实现，队列元素动态分配空间
动态扩展，适合不确定大小的队列
节点管理复杂，增加了内存开销