数据结构 之 队列习题 力扣oj(附加思路版)

优先级队列 

#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;
    }
};

队列

周末舞会 

思路：        

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

#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();//都为空才为空
    }
};