在数据结构中，队列（Queue）是一种特殊的线性表，只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以又称为先进先出（FIFO—First In First Out）的线性表。
队列通常使用链表或数组来实现。在链表中，我们通常使用两个指针，一个指向队首，另一个指向队尾，以方便进行入队和出队操作。在数组中，我们通常维护两个变量，一个指向队首元素的位置，另一个指向队尾元素的后一个位置，即队列的下一个空位。
除了基本的队列外，还有一些特殊的队列类型，如循环队列和双端队列。
1. 循环队列：为了避免队满时无法入队以及队空时无法出队的问题，我们可以使用循环队列。循环队列将数组的首尾相连，形成一个环，当队尾指针到达数组的末尾时，下一个位置就是数组的开始。
2. 双端队列：双端队列允许在队列的两端进行入队和出队操作。这使得双端队列不仅具有队列的特性，还具有栈的特性。
入队与出队操作如下：
1. 入队操作：在队列的尾部插入一个新元素。在循环队列中，如果队尾指针到达数组的末尾，则将其重置为数组的开始位置，然后插入新元素。
2. 出队操作：从队列的头部删除一个元素。在循环队列中，如果队头指针到达数组的末尾，则将其重置为数组的开始位置，然后删除元素。
以下是一个使用数组实现的循环队列的C++代码示例，代码如下：
#include <iostream>
using namespace std;
const int MAX_SIZE = 10; // 队列的最大容量
class CircularQueue {
private:
int front; // 队首指针
int rear; // 队尾指针
int queue[MAX_SIZE]; // 队列数组
public:
CircularQueue() {
front = rear = -1; // 初始化队列为空
}
// 判断队列是否为空
bool isEmpty() {
return front == -1;
}
// 判断队列是否已满
bool isFull() {
return (rear + 1) % MAX_SIZE == front;
}
// 入队操作
void enqueue(int value) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
if (isEmpty()) {
front = 0;
}
rear = (rear + 1) % MAX_SIZE;
queue[rear] = value;
}
// 出队操作
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
if (front == rear) { // 如果队列中只有一个元素
front = rear = -1;
} else {
front = (front + 1) % MAX_SIZE;
}
}
// 获取队首元素
int peekFront() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1;
}
return queue[front];
}
// 获取队尾元素
int peekRear() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1;
}
return queue[rear];
}
// 打印队列元素
void printQueue() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
cout << "Queue elements: ";
int current = front;
do {
cout << queue[current] << " ";
current = (current + 1) % MAX_SIZE;
} while (current != front);
cout << endl;
}
};
int main() {
CircularQueue q;
// 入队操作
q.enqueue(1);q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
// 打印队列元素
q.printQueue(); // 应输出：Queue elements: 1 2 3 4 5
// 出队操作
q.dequeue();
q.dequeue();
// 打印队列元素
q.printQueue(); // 应输出：Queue elements: 3 4 5
// 获取队首元素
cout << "Front element: " << q.peekFront() << endl; // 应输出：Front element: 3
// 获取队尾元素
cout << "Rear element: " << q.peekRear() << endl; // 应输出：Rear element: 5
// 再次入队操作
q.enqueue(6);
q.enqueue(7);
q.enqueue(8);
// 打印队列元素
q.printQueue(); // 应输出：Queue elements: 3 4 5 6 7 8
return 0;
}结果如下所示：
注意循环队列满的情况：由于我们在这里使用了一个固定大小的数组，并且队列大小已经达到了最大值，所以再试图入队会导致队列满。在实际应用中，可能需要一个动态大小的队列或者其他机制来处理队列满的情况。
本文详细介绍了C++中的队列概念，特别是先进先出（FIFO）的数据结构。队列有多种类型，包括循环队列和双端队列等。我们通过实现一个循环队列的示例，展示了队列的基本操作，如入队、出队、查看队首和队尾元素等。循环队列通过模运算实现了空间的循环使用，提高了队列的利用率。然而，循环队列的实现也有其局限性，如需要预先确定队列的最大容量，当队列满时可能无法继续入队等。在实际应用中，需要根据具体需求选择合适的队列实现方式。
