用队列来实现栈-力扣题

本文主要是介绍用队列来实现栈-力扣题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现自己做这种题，真的是太慢了，不过做出来就很开心了。自己在做的时候，没有想到交换队列v1和v2这一步，其实直接交换，就不需要判断应该从v1还是v2入队了。始终保证空队列为固定不变的队列。
题目：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。
要求：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
注意这里不能使用队列里面的back函数。
方法1：
1.一个队列v1来存储队列中原本就有的元素，队列v2作为临时栈来存储要入栈的元素。
将v1队列中的元素循环出栈，直到v1为空，将元素入队v2。
之后交换v1和v2队列，v2为空，保证下次仍然从v2插入。
出栈的话：只需v1.pop()即可，而获取栈顶元素同理v1.front()即可。
画图解释：

代码如下：

class MyStack {
public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {v2.push(x);//v1中的元素循环入队v2，直到v1中元素为空。while (!v1.empty()){v2.push(v1.front());v1.pop();//}swap(v1, v2);//交换v1和v2队列，保证v2为空，下次仍然从v2入栈。}/** Removes the element on top of the stack and returns that element. */int pop() {int ret = v1.front();v1.pop();return ret;}/** Get the top element. */int top() {return v1.front();}/** Returns whether the stack is empty. */bool empty() {return v1.empty();}
private:queue<int> v1;queue<int> v2;};

方法2：
元素从v1入栈，保证v1队列中的元素只剩下1个，即为栈顶元素。
获取栈顶元素的时候，注意获取v1的队头元素之后，需要将v1中的元素入队v2，不能删除原来队列中的元素。再清空v1。代码如下所示：

class MyStack {
public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {v1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {//保证v1中剩余1个元素，其他元素入队v2;while (v1.size()>1){v2.push(v1.front());v1.pop();}//获取栈顶元素int ret = v1.front();v1.pop();//交换v1和v2队列，保证v2始终为空队列;swap(v1, v2);return ret;}/** Get the top element. */int top() {while (v1.size()>1){v2.push(v1.front());v1.pop();}int ret = v1.front();v2.push(v1.front());v1.pop();swap(v1, v2);//清空v2;// while (!v2.empty())// {// 	v2.pop();// }return ret;}/** Returns whether the stack is empty. */bool empty() {return v1.empty();}
private:queue<int> v1;queue<int> v2;};

这篇关于用队列来实现栈-力扣题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---