优先级队列 

#include<queue> --队列 和 优先级队列的头文件

优先级队列： 堆结构 最大堆 和 最小堆

相关函数：
    front() 获取第一个元素
    back() 获取最后一个元素
    push() 放入元素
    pop() 弹出第一个元素
    size() 计算队列中元素的个数
    empty() 判断是否为空 为空返回true 不为空返回false

石头的重量

1046. 最后一块石头的重量https://leetcode.cn/problems/last-stone-weight/

---

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

思路

        利用优先级，队列默认最大堆结构将数组中元素升序排一下，然后每次取出堆顶元素和堆顶下一位，用两个变量接收（利用top和pop函数）。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> q;for(int i=0; i<stones.size(); i++){q.push(stones[i]);}while(q.size()>1){int x=q.top();q.pop();int y=q.top();q.pop();if(x != y) {q.push(x-y);}}if(q.empty()) {return 0;} else {return q.top();}}
};

---

分发饼干 

455. 分发饼干https://leetcode.cn/problems/assign-cookies/

        假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。4

与上题思路相同 

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {priority_queue<int> g_que,s_que;int res=0;for(int i=0;i<g.size();i++){g_que.push(g[i]);}for(int i=0;i<s.size();i++){s_que.push(s[i]);}while(!s_que.empty()&&!g_que.empty())//当同时存在时{if(g_que.top()<= s_que.top()){res++;g_que.pop();s_que.pop();}elseg_que.pop();}return res;}
};

---

 

面试题：最小k个数 

面试题 17.14. 最小K个数https://leetcode.cn/problems/smallest-k-lcci/

提示

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

思路

        创建一个队列（队列默认最大堆结构），将前k个始终维护成最大堆结构，k~arr.size()-1中每个元素始终与栈顶元素作比较，最终队列即为所求。

        如果用最小堆的话，当数据量非常大时，时间复杂度太高了。

class Solution {
public:vector<int> smallestK(vector<int>& arr, int k) {if(k==0||arr.size()==0)return {};priority_queue<int> que;vector<int>res;for(int i=0;i<k;i++)que.push(arr[i]);for(int i=k;i<arr.size();i++){if(arr[i]<que.top()){que.pop();que.push(arr[i]);}}while(!que.empty()){res.push_back(que.top());que.pop();}return res;}
};

---

 

队列

周末舞会 

1332：【例2-1】周末舞会 【题目描述】         假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。 【输入】         第一行两队的人数;         第二行舞曲的数目。 【输出】         配对情况。

思路：        

        这段代码通过两个队列分别表示舞会上的男士和女士队伍，循环读取舞曲数目来模拟配对跳舞的过程。对于每首舞曲，从男女队列的队首分别取出一个人配对为舞伴，然后将这对舞伴放回队列的末尾以便参与下一轮配对，直至所有舞曲播放完毕。这样，通过队列的先进先出特性，实现了一个简单的舞伴轮换配对模拟。

#include<iostream>
#include<queue>//栈的头文件
using namespace std;int main()
{int m, n, k;cin >> m >> n >> k;queue<int>s1;queue<int>s2;for (int j = 1; j <= m; j++){s1.push(j);}for (int c = 1; c <= n; c++){s2.push(c);}for (int i = 1; i <= k; i++){cout << s1.front() << s2.front() << endl;int x = s1.front(), y = s2.front();s1.pop(); s2.pop();s1.push(x), s2.push(y);}return 0;
}

---

面试题--用两个队列实现栈 

225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路

        这段代码通过两个队列`q1`和`q2`来模拟一个后入先出（LIFO）的栈结构。当新元素被加入（`push`操作）时，它直接进入`q1`。为了模拟栈的`pop`操作，代码将`q1`中的元素，除了最后一个加入的元素之外，都转移到`q2`中，这样`q1`中剩下的最后一个元素就是需要被`pop`的元素。在这个元素被移除后，`q2`的内容回到`q1`，实现了后入先出的逻辑。`top`操作简单地返回`q1`的最后一个元素，而`empty`操作检查`q1`是否为空，从而判断栈是否为空。

class MyStack {
public:queue<int>q1;queue<int>q2;void push(int x) {q1.push(x);}int pop() {while(q1.size()>1)//队列中只剩下一个元素{q2.push(q1.front());q1.pop();}int x=q1.front();//记录最后一个元素 即返回值q1.pop();q1=q2;while(!q2.empty())//清空q2{q2.pop();}return x;}int top() {return q1.back();}bool empty() {return q1.empty();}
};

---

 

面试题--用两个栈实现队列

232. 用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

 思路

        这段代码使用两个栈`s1`和`s2`来实现一个队列。当元素被推入队列时，它被压入`s1`。要执行`pop`或`peek`操作时，如果`s2`为空，`s1`的所有元素逆序转移到`s2`中，使得`s1`的底部元素移动到`s2`的顶部，即队列的前端。这样，从`s2`中弹出或查看顶部元素就可以模拟队列的`pop`和`peek`操作。`empty`操作通过检查两个栈是否都为空来判断队列是否为空，实现了一个先入先出的队列行为。

class MyQueue {
public:
/*先将栈中元素除了最后一个取出*/
stack<int>s1;
stack<int>s2;void push(int x) {s1.push(x);}int pop() {if(s2.empty())//s2不为空的话直接删除，为空将s1中元素全部放入s2{while(!s1.empty()){s2.push(s1.top());s1.pop();}}int x=s2.top();s2.pop();return x;}int peek() {if(s2.empty())//s2不为空的话直接删除，为空将s1中元素全部放入s2{while(!s1.empty()){s2.push(s1.top());s1.pop();}}int x=s2.top();return x;}bool empty() {return s1.empty()&&s2.empty();//都为空才为空}
};