本文主要介绍队列（queue）的相关力扣题目。
一、设计队列
232. 用栈实现队列（简单难度）
剑指 Offer 09. 用两个栈实现队列（简单难度）
面试题 03.04. 化栈为队（简单难度）
class MyQueue {
public:
stack<int> stIn;//进栈
stack<int> stOut;//出栈
MyQueue() {}
bool empty() {return stIn.empty() && stOut.empty();}
//进栈存入元素
void push(int x) {stIn.push(x);}
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if(stOut.empty()){
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
};
二、循环队列
622. 设计循环队列 (中等难度)
class MyCircularQueue {
private:
int mCapacity;
int mSize;
int * array;
int first;
int last;
public:
MyCircularQueue(int k) {
mCapacity=k;
array=new int[mCapacity];
first=0;
last=0;
mSize=0;
}
~MyCircularQueue() {
delete [] array;
}
// 入队
bool enQueue(int value) {
if(isFull()) return false;
if(last==mCapacity-1){
array[last]=value;
last=0;
}
else{
array[last++]=value;
}
mSize++;
return true;
}
// 出队
bool deQueue() {
if(isEmpty()) return false;
if(first==mCapacity-1){
first=0;
}else{
first++;
}
mSize--;
return true;
}
int Front() {
if(isEmpty()) return -1;
return array[first];
}
int Rear() {
if(isEmpty()) return -1;
if(last==0) return array[mCapacity-1];
return array[last-1];
}
bool isEmpty() {
if(mSize==0) return true;
return false;
}
bool isFull() {
if(mSize==mCapacity)return true;
return false;
}
};
641. 设计循环双端队列(中等难度)
class MyCircularDeque {
private:
int mSize;
int mCapacity;
int first;
int last;
int * array;
public:
MyCircularDeque(int k) {
mCapacity=k;
array=new int[mCapacity];
mSize=0;
first=0;
last=0;
}
~MyCircularDeque() {
delete [] array;
}
//入队首
bool insertFront(int value) {
if(isFull()) return false;
if(first==0){
first=mCapacity-1;
array[first]=value;
}else{
first--;
array[first]=value;
}
mSize++;
return true;
}
//入队尾
bool insertLast(int value) {
if(isFull()) return false;
if(last==mCapacity-1){
array[last]=value;
last=0;
}else{
array[last]=value;
last++;
}
mSize++;
return true;
}
//出队首
bool deleteFront() {
if(isEmpty()) return false;
if(first==mCapacity-1) first=0;
else first++;
mSize--;
return true;
}
//出队尾
bool deleteLast() {
if(isEmpty()) return false;
if(last==0) last=mCapacity-1;
else last--;
mSize--;
return true;
}
int getFront() {
if(isEmpty()) return -1;
else return array[first];
}
int getRear() {
if(isEmpty()) return -1;
if(last==0) return array[mCapacity-1];
else return array[last-1];
}
bool isEmpty() {
if(mSize==0) return true;
return false;
}
bool isFull() {
if(mSize==mCapacity) return true;
return false;
}
};
1670. 设计前中后队列(中等难度)
class FrontMiddleBackQueue {
private:
vector<int> array;// 数组
public:
FrontMiddleBackQueue() {}
void pushFront(int val) {array.insert(array.begin(),val);}
void pushBack(int val) {array.push_back(val);}
void pushMiddle(int val) {
int len=array.size();
int mid=len/2;
array.insert(array.begin()+mid,val);
}
int popFront() {
if (array.empty()) return -1;
int res=array.front();
array.erase(array.begin());
return res;
}
int popMiddle() {
if (array.empty()) return -1;
int len=array.size();
int mid=(len-1)/2;
int res=array[mid];
array.erase(array.begin()+mid);
return res;
}
int popBack() {
if (array.empty()) return -1;
int res=array.back();
array.pop_back();
return res;
}
};
三、单调队列
剑指 Offer 59 - II. 队列的最大值(中等难度)
本题的解题思路：定义一个普通队列queue用于正常出入队，一个双端队列deque用于存放最大元素。
比如，连续放入三个元素1，2,3，那么queue里面就是1,2,3,，但是deque只存最大值3在队头
再比如1,2,3,4,5,4,1,2,3
按照这个顺序入队，那么deque只需存放5,4,3
class MaxQueue {
private:
queue<int> que; // 普通队列
deque<int> deq; // 双端队列
public:
MaxQueue() {}
// 获取最大值
int max_value() {
if(que.empty()) return -1;
return deq.front();
}
// 入队
void push_back(int value) {
que.push(value);//普通队列入队
//加入双端队列之前，将其中小于value的值都弹出
while(!deq.empty()&&deq.back()<value)
deq.pop_back();
deq.push_back(value);//双端队列入队
}
// 出队
int pop_front() {
if(que.empty()) return -1;
// 普通队列弹出一个元素
int a=que.front();
que.pop();
// 如果双端队列的队首元素和当前弹出的元素相等，则一起弹出
if(a==deq.front())
deq.pop_front();
return a;
}
};
剑指 Offer 59 - I. 滑动窗口的最大值（困难难度）
239. 滑动窗口最大值（困难难度）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 方法一：优先级队列
// int n = nums.size();
// if(n==0) return {};
// priority_queue<pair<int, int>> q;//最大堆
// // 首先将数组的前k个元素放入堆中
// for (int i = 0; i < k; ++i) q.emplace(nums[i], i);//emplace相当于insert
// vector<int> ans = {q.top().first};
// // 滑动窗口开始移动，等同于遍历[k,n)
// for (int i = k; i < n; ++i) {
// q.emplace(nums[i], i);//将当前数加入堆中
// // 将滑动窗口外的数去掉
// while (q.top().second <= i - k) q.pop();
// ans.push_back(q.top().first);
// }
// return ans;
// 方法二：单调队列
int n = nums.size();
if(n==0) return {};
deque<int> que;// 单调队列，保存索引，队首到队尾从大到小排列
// 先将数组的[0,k)加入单调队列
for (int i = 0; i < k; ++i) {
// 新入队尾元素nums[i]，队中所有比nums[i]小是数都得出队
while (!que.empty() && nums[i] >= nums[que.back()]) que.pop_back();
que.push_back(i);
}
vector<int> res = {nums[que.front()]};
// 将数组的[k,n)依次加入单调队列
for (int i = k; i < n; ++i) {
// 加入单调队列
while (!que.empty() && nums[i] >= nums[que.back()]) que.pop_back();
que.push_back(i);
// 将滑动窗口以外的数移除单调队列
while (que.front() <= i - k) que.pop_front();
res.push_back(nums[que.front()]);
}
return res;
}
};
四、优先级队列
1046. 最后一块石头的重量 （简单难度）
这道题每回合要从一堆石头中取出最重的2个石头，从只要知道优先级队列的存在，思路和代码应该就很容易，借助优先级队列我们可以很容易的给出编码，思路容易，编码要多写几遍，好好打磨自己的代码：
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> queue; // 最大堆
for(auto stone:stones) queue.push(stone);//遍历加入堆
while(queue.size()>1){
int x=queue.top();//最大值
queue.pop();
int y=queue.top();//次大值
queue.pop();
queue.push(x-y);
}
return queue.empty()?0:queue.top();
}
};
剑指 Offer 40. 最小的k个数 （简单难度）
面试题 17.14. 最小K个数（中等难度）
这道题的难点在于如何初始化一个可以存储哈希映射的最小堆
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(arr.size()==0) return arr;
vector<int> result;
priority_queue<int,vector<int>,greater<int> > min_heap;//最小堆
for(auto a:arr) min_heap.push(a);
while(k--){
result.push_back(min_heap.top());
min_heap.pop();
}
return result;
}
};
347. 前 K 个高频元素（中等难度）
剑指 Offer II 060. 出现频率最高的 k 个数字（中等难度）
该2道题考察的都是出现频率最多的几个数，一说到频率，自然想到要使用哈希表来解决，首先要统计出各个数字出现的频率。为了找出频率最高的前k个数字，需要使用优先级队列建立一个最小堆（将小值移除）。维护一个长度适中为k的最小堆，扫描一遍哈希表后，优先级队列中剩余的就是频率最高的前k个数字。
class Solution {
public:
class mycomparison{
public:
bool operator()(const pair<int,int>& a,const pair<int,int>& b){
return a.second>b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计频率
unordered_map<int,int> map;
for(auto num:nums){
map[num]++;
}
// 找出前k个高频
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> min_heap;
for(auto it = map.begin(); it != map.end(); it++) // 遍历哈希表
{
min_heap.push(*it);
if(min_heap.size()>k){
min_heap.pop();
}
}
// 构建结果
vector<int> result;
while (!min_heap.empty()) {
result.push_back(min_heap.top().first) ;
min_heap.pop();
}
return result;
}
};
295. 数据流的中位数（困难难度）
剑指 Offer 41. 数据流中的中位数（困难难度）
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> queMin;//记录小于等于中位数的数
priority_queue<int, vector<int>, greater<int>> queMax;//记录大于中位数的数
MedianFinder() {}
void addNum(int num) {
//此时num 小于等于中位数，我们需要将该数添加到queMin 中。
//新的中位数将小于等于原来的中位数，
//因此我们可能需要将queMin中最大的数移动到queMax中
if (queMin.empty() || num <= queMin.top()) {
queMin.push(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.push(queMin.top());
queMin.pop();
}
}
//此时num 大于中位数，我们需要将该数添加到queMin 中。
//新的中位数将大于等于原来的中位数，
//因此我们可能需要将queMax 中最小的数移动到queMin中
else {
queMax.push(num);
if (queMax.size() > queMin.size()) {
queMin.push(queMax.top());
queMax.pop();
}
}
}
double findMedian() {
if (queMin.size() > queMax.size()) return queMin.top();
return (queMin.top() + queMax.top()) / 2.0;
}
};