医院行业网站,快手等视频网站做推广,免费注册网站网址,菏泽网站建设培训学校封装#xff1a; std::queue 在底层容器的基础上 提供了封装。默认情况下#xff0c;std::queue 使用 std::deque 作为其底层容器#xff0c;但也可以配置为使用 std::list 或 其他符合要求的容器
时间复杂度#xff1a; 入队和出队操作 通常是 常数时间复杂度#xff08…封装 std::queue 在底层容器的基础上 提供了封装。默认情况下std::queue 使用 std::deque 作为其底层容器但也可以配置为使用 std::list 或 其他符合要求的容器
时间复杂度 入队和出队操作 通常是 常数时间复杂度O(1)这意味着 操作的时间不会随着队列大小的增加 而显著增加 空间复杂度 由于 std::queue 使用底层容器来存储元素其空间复杂度 取决于 所使用的底层容器
例如使用 std::deque 时空间复杂度通常是线性的O(n)其中 n 是队列中元素的数量
1、实现
template typename T, typename Container std::dequeT
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内容在此基础上整理补充
