简易STL实现 | Queue 的实现

封装： std::queue 在底层容器的基础上 提供了封装。默认情况下，std::queue 使用 std::deque 作为其底层容器，但也可以配置为使用 std::list 或 其他符合要求的容器

时间复杂度： 入队和出队操作 通常是 常数时间复杂度（O(1)），这意味着 操作的时间不会随着队列大小的增加 而显著增加
空间复杂度： 由于 std::queue 使用底层容器来存储元素，其空间复杂度 取决于 所使用的底层容器

例如，使用 std::deque 时，空间复杂度通常是线性的（O(n)），其中 n 是队列中元素的数量

1、实现

template <typename T, typename Container = std::deque<T>>
class MyQueue {
private:Container data; // 使用底层容器存储队列的元素public:// 将元素添加到队尾void push(const T& value) {data.push_back(value);}// 移除队头元素void pop() {if (!empty()) {data.pop_front();} else {throw std::runtime_error("Queue is empty.");}}// 访问队头元素的引用T& front() {if (!empty()) {return data.front();} else {throw std::runtime_error("Queue is empty.");}}// 访问队尾元素的引用T& back() {if (!empty()) {return data.back();} else {throw std::runtime_error("Queue is empty.");}}// 检查队列是否为空bool empty() const {return data.empty();}// 返回队列的大小size_t size() const {return data.size();}
};

2、常见面试题

1、阻塞队列 在队列为空时 会阻塞出队操作，在队列满时 会阻塞入队操作。非阻塞队列 不会阻塞线程；如果 操作不能立即进行，则会失败 或 返回特定值

2、循环队列的实现
循环队列 可以使用 一个固定大小的数组 和 两个指针（头指针和尾指针，前闭后闭）来实现。当尾指针到达数组的末尾时，它会循环回到数组的开始位置。循环队列的优势 在于它可以重复使用空间，减少了 因为扩容而带来的性能开销

所有 + 的地方 要加上 % size
有两个重要条件：
队列为空：当 front == -1
队列已满：当 (rear + 1) % size == front

#include <iostream>
using namespace std;class CircularQueue {
private:int *queue;    // 动态数组存储队列元素int front;     // 指向队列头部的索引int rear;      // 指向队列尾部的索引int size;      // 队列容量public:// 构造函数，初始化队列CircularQueue(int maxSize) {size = maxSize;queue = new int[size];front = -1;rear = -1;}// 析构函数，释放动态内存~CircularQueue() {delete[] queue;}// 检查队列是否为空bool isEmpty() {return (front == -1);}// 检查队列是否已满bool isFull() {return ((rear + 1) % size == front);}// 向队列中插入元素void enqueue(int value) {if (isFull()) {cout << "队列已满，无法插入元素 " << value << endl;return;}if (isEmpty()) {front = 0; // 如果队列为空，则插入第一个元素时将 front 指向 0}rear = (rear + 1) % size; // 更新 rear 为下一个位置（循环）queue[rear] = value;cout << "插入元素: " << value << endl;}// 从队列中删除元素int dequeue() {if (isEmpty()) {cout << "队列为空，无法删除元素" << endl;return -1;}int value = queue[front];if (front == rear) {// 队列中只有一个元素，删除后队列为空front = -1;rear = -1;} else {// 更新 front 为下一个位置（循环）front = (front + 1) % size;}cout << "删除元素: " << value << endl;return value;}// 获取队列头部的元素int peekFront() {if (isEmpty()) {cout << "队列为空，无法获取头部元素" << endl;return -1;}return queue[front];}// 获取队列尾部的元素int peekRear() {if (isEmpty()) {cout << "队列为空，无法获取尾部元素" << endl;return -1;}return queue[rear];}// 显示队列中的元素void displayQueue() {if (isEmpty()) {cout << "队列为空" << endl;return;}cout << "队列元素: ";int i = front;while (true) {cout << queue[i] << " ";if (i == rear) {break;}i = (i + 1) % size;}cout << endl;}
};

https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充