队列
队列是一种先进先出表，也就是说它的插入在一端进行，而删除则在另一端进行。
队列模型
队列的基本操作有入队（enqueue），出队（dequeue）。入队就是在队尾（rear）插入一个元素，出队就是在队头（front）删除并返回一个元素。
队列的实现
根栈一样，队列可以使用任何实现表的方法来实现，包括链表，数组，vector。下面我们来依次看一下分别如何实现。
链表实现队列
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class QueueUsingList {
private:
ListNode* front;
ListNode* rear;
public:
QueueUsingList() : front(nullptr), rear(nullptr) {}
// 入队操作
void enqueue(int value) {
ListNode* newNode = new ListNode(value);
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
// 出队操作
int dequeue() {
if (front == nullptr) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
int value = front->val;
ListNode* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return value;
}
// 查看队首元素
int peek() {
if (front == nullptr) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
return front->val;
}
// 检查队列是否为空
bool isEmpty() {
return front == nullptr;
}
};
首先定义了一个链表中的节点的结构体，我们在前面其实了解过，节点包括一个数值和一个next指针。
接着定义了一个QueueUsingList 类实现了基于链表的队列。其中：
front和rear分别指向队列的队首和队尾。enqueue方法创建新节点，将其添加到队尾。若队列为空，同时更新front和rear；若不为空，只更新rear。dequeue方法移除队首元素，更新front，并释放原队首节点的内存。若队列为空，输出错误信息。peek方法返回队首元素的值，若队列为空，输出错误信息。isEmpty方法通过检查front是否为nullptr来判断队列是否为空。
数组实现队列
#include <iostream>
#include <array>
#include <cassert>
const int MAX_SIZE = 100; // 假设队列最大容量为 100
class QueueUsingArray {
private:
std::array<int, MAX_SIZE> arr;
int front;
int rear;
int size;
public:
QueueUsingArray() : front(0), rear(0), size(0) {}
// 入队操作
void enqueue(int value) {
assert(size < MAX_SIZE); // 确保队列未满
arr[rear] = value;
rear = (rear + 1) % MAX_SIZE;
size++;
}
// 出队操作
int dequeue() {
if (size == 0) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
int value = arr[front];
front = (front + 1) % MAX_SIZE;
size--;
return value;
}
// 查看队首元素
int peek() {
if (size == 0) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
return arr[front];
}
// 检查队列是否为空
bool isEmpty() {
return size == 0;
}
};
这里指定了队列的最大容量为100，实际写代码过程中可以根据实际情况进行调整。
这里直接定义了一个QueueUsingArray 类，使用 std::array 存储队列元素，front 指向队首元素，rear 指向队尾元素的下一个位置。其中：
enqueue方法将元素添加到rear位置，并更新rear指针，使用取模运算实现循环队列。dequeue方法移除队首元素，更新front指针，使用取模运算实现循环队列。peek方法返回队首元素，若队列为空，输出错误信息。isEmpty方法通过检查size是否为 0 来判断队列是否为空。
在数组实现中，我们使用了**循环数组（circular array）**实现，因为一个数组的空间是有限的，不管用不用，c++已经把这部分内存分给了数组，那么试想如果我们不断的入队出队，数组的前端是不是会出现大量的空位置，而可利用的空间越来越少，直至最后一个，而如果让rear指针再往后移就会越界，所以我们采用循环数组，让rear指针指向最后一个的下一个位置时返回数组的开头，也就是第一个位置，这样就避免越界和可以重复使用数组空间。
如下图模拟了一个循环数组实现队列的过程：
vector实现数组
#include <iostream>
#include <vector>
class QueueUsingVector {
private:
std::vector<int> v;
public:
// 入队操作
void enqueue(int value) {
v.push_back(value);
}
// 出队操作
int dequeue() {
if (v.empty()) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
int value = v.front();
v.erase(v.begin());
return value;
}
// 查看队首元素
int peek() {
if (v.empty()) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
return v.front();
}
// 检查队列是否为空
bool isEmpty() {
return v.empty();
}
};
QueueUsingVector 类使用 std::vector 存储队列元素，其中：
enqueue方法使用push_back向vector尾部添加元素。dequeue方法使用erase移除vector的第一个元素，获取其值。若队列为空，输出错误信息。peek方法使用front方法获取队首元素，若队列为空，输出错误信息。isEmpty方法通过v.empty()判断队列是否为空。
总结
上述的三种方法实现队列中，使用数组实现的队列为循环队列，最大容量为 MAX_SIZE，使用链表和 vector 实现的队列则可以动态扩容。无论哪种方法实现队列，复杂度都是O(1)，非常高效。
那么同栈一样，c++的STL库中一样提供了queue库来供我们直接使用，下面一起来看看吧
STL库中的队列（queue）
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
// 入队操作
q.push(1);
q.push(2);
q.push(3);
// 查看队首元素
std::cout << "Front element: " << q.front() << std::endl;
// 出队操作
q.pop();
std::cout << "Front element after pop: " << q.front() << std::endl;
// 队列大小
std::cout << "Queue size: " << q.size() << std::endl;
// 检查队列是否为空
if (q.empty()) {
std::cout << "Queue is empty." << std::endl;
} else {
std::cout << "Queue is not empty." << std::endl;
}
return 0;
}
相较于上面三种我们自己实现，直接使用封装好的queue库显然更简单。
q.push(1);：将元素1入队。q.front();：返回队首元素，但不将其从队列中移除。q.pop();：将队首元素从队列中移除。q.size();：返回队列中元素的数量。q.empty();：检查队列是否为空，如果队列为空，返回true，否则返回false。
拓展
std::queue 是一个容器适配器，它默认使用 std::deque 作为底层容器，但也可以使用其他容器，如 std::list 或 std::vector。比如使用 std::list 作为底层容器：
std::queue<int, std::list> q;
只用更改定义队列这一行即可，其它使用接口和方法默认一样。但是我们不建议更改底层容器，因为 std::deque 在性能上对于**队列的操作（入队和出队）**具有较好的平衡，特别是对于频繁在两端插入和删除元素的情况。std::queue默认使用std::deque作为底层容器，这是因为std::deque具有以下优点：
- 可以高效地在两端进行插入和删除操作，时间复杂度为
O(1)。 - 提供了动态的空间分配，不会像
std::vector那样在内存增长时需要大量的复制操作。 - 不像
std::list那样每个元素需要额外的指针存储，相对更节省内存空间。
选择不同底层容器的考虑因素：
std::list作为底层容器：- 当需要频繁的插入和删除元素，尤其是在队列中间进行插入和删除操作时，使用
std::list作为底层容器会更合适。 std::list对元素的插入和删除操作具有 的时间复杂度，不会像std::vector那样引起元素的大量移动。- 然而，
std::list会使用额外的内存来存储节点之间的指针，每个元素的存储开销相对较大。
- 当需要频繁的插入和删除元素，尤其是在队列中间进行插入和删除操作时，使用
std::vector作为底层容器：- 如果对内存使用较为敏感，且入队操作不会频繁导致
std::vector扩容，使用std::vector作为底层容器可以节省一些额外的指针空间。 - 但是，
std::vector在扩容时会涉及到元素的复制或移动，这可能会导致性能下降。如果入队操作频繁导致std::vector不断扩容，性能会受到一定影响。
- 如果对内存使用较为敏感，且入队操作不会频繁导致
std::deque作为底层容器（默认）：- 通常情况下，
std::deque是一个不错的折衷选择，它在两端的操作性能都比较好，既避免了std::vector扩容时的复制开销，又不像std::list那样需要额外的指针存储。
- 通常情况下，
总结：
std::queue的底层容器选择取决于具体的应用场景和性能需求。- 对于大多数情况，使用默认的
std::deque可以满足需求，它在性能和内存使用上取得了较好的平衡。 - 若需要频繁的元素插入和删除操作，可以考虑使用
std::list。 - 若对内存使用比较敏感且对性能有一定的要求，可以根据实际情况考虑使用
std::vector，但需要注意扩容带来的性能开销。
无论使用哪种底层容器，std::queue 提供的接口都是相同的，这保证了代码的一致性和可移植性，方便开发者根据不同的需求灵活选择底层容器。