剑指offer：用两个栈来实现一个队列

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

题目：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

 

思路：

stack1用来入队列，stack2用来出队列。每当有元素入队列时，直接入stack1；如果要出队列，首先判断stack2是否为空，如果不是，直接弹出stack2栈顶元素，如果是空栈，先将stack1中元素全部弹出到stack2，然后弹出stack2栈顶元素。

补充背景知识：stack的常用操作，stack.push(x)，stack.pop()，stack.empty()，stack.top()

queue的常用操作，queue.push(x)，queue.pop()，queue.empty()，queue.front()，queue.back()，queue.size()

代码：

在线测试OJ：

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

AC代码：

class Solution
{
public:void push(int node) {stack1.push(node);}int pop() {if(stack2.empty()){if(stack1.empty())return -10000; //栈顶为空还要弹出的错误情况else{while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}}int temp = stack2.top();stack2.pop();return temp;}private:stack<int> stack1;stack<int> stack2;
}; 

扩展：用两个队列实现一个栈

思路：

方法1：当有元素入栈时，先入队列queue1。当有元素出栈时，先将queue1中前n-1个元素出队列并入队列2，然后让最后剩下的一个元素出队列，完成出栈，之后还需要将queue2中元素全部出队列并入queue1，以便下一元素入栈的顺序是正确的。这样做的缺点是元素需要反复进行出入队列操作，效率不高。

方法2：两个队列交替使用，当有元素入栈时，把它压入非空队列（起始两个队列都为空，任选一个入队列即可）。出栈时，将非空队列的元素依次出队列并压入另一个空队列，然后将剩下的最后一个元素弹出，完成出栈操作。

class MyStack {
public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {if(q1.empty()&&q2.empty())q1.push(x);else if(q1.empty()&&!q2.empty())q2.push(x);else if(!q1.empty()&&q2.empty())q1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {if(q2.empty()){while(q1.size()>1){q2.push(q1.front());q1.pop();}int temp=q1.front();q1.pop();return temp;}else{while(q2.size()>1){q1.push(q2.front());q2.pop();}int temp=q2.front();q2.pop();return temp;}}/** Get the top element. */int top() {if(!q1.empty())return q1.back();elsereturn q2.back();}/** Returns whether the stack is empty. */bool empty() {return (q1.empty()&&q2.empty());}
private:queue<int> q1;queue<int> q2;};/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* bool param_4 = obj.empty();*/

 

这篇关于剑指offer：用两个栈来实现一个队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---