优先级队列
#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();
}
else
g_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();//都为空才为空
}
};
![[网鼎杯2018]Unfinish 两种方法 -----不会编程的崽](https://img-blog.csdnimg.cn/direct/fb7562581ba54ae1967c18eed89e79fc.png)
