首页 > 试题广场 > 用两个栈实现队列
[编程题]用两个栈实现队列
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

1271个回答

添加回答
推荐
class Solution 
   查看全部
编辑于 2015-08-18 23:15:03 回复(46)
这是左程云的《程序员代码面试指南》的答案:
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
    	if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

发表于 2016-06-04 16:11:14 回复(37)
思路:
  • 栈A用来作入队列
  • 栈B用来出队列,当栈B为空时,栈A全部出栈到栈B,栈B再出栈(即出队列)
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
        
    def push(self, node):
        # write code here
        self.stackA.append(node)
        
    def pop(self):
        # return xx
        if self.stackB:
            return self.stackB.pop()
        elif not self.stackA:
            return None
        else:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
            return self.stackB.pop()

编辑于 2016-07-24 09:39:31 回复(13)
//每次psuh是时先将stack2清空放入stck1(保证选入的一定在栈底),stack2始终是用来删除的
//在pop前,先将stack1中中的数据清空放入stack2(保存后入的在栈底),stack1始终用于push
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
	    	while(!stack2.isEmpty()){
	    		stack1.push(stack2.pop());
	    	}
	       stack1.push(node);
	    }
	    
	    public int pop() {
	    	while (!stack1.isEmpty()){
	    		stack2.push(stack1.pop());
	    	}
	    	return stack2.pop();
	    }
}
发表于 2016-09-30 11:38:09 回复(6)
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if len(self.stack2) > 0:
            return self.stack2.pop()
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        if len(self.stack2) > 0:
            return self.stack2.pop()

发表于 2018-02-27 22:05:52 回复(1)
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
   public void push(int node) {
        stack1.push(node);
    }
    
    
   public int pop() {
       
       while(!stack2.isEmpty())
        {
            return stack2.pop();
        }
        
        while(!stack1.isEmpty())
        {
            stack2.push(stack1.pop());
        }
       
        return stack2.pop();
    }
}

发表于 2015-04-13 08:21:53 回复(6)
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
 stack1.push(new Integer(node));
 }

 public int pop() {
 if(stack2.empty()){
 while(!stack1.empty()){
 stack2.push(stack1.pop());
 }
 }
 if(stack2.empty())
 System.out.println("stack1 is empty!");
 
 return stack2.pop().intValue();

 } 
}

发表于 2015-04-11 10:41:38 回复(4)
最佳答案:通过所有测试用例的代码:思路:有两个栈,栈1和栈2.当入栈的时候,我们将它全放进栈1中,当需要出栈的时候,我们将栈1出栈到栈2中,然后再将栈2依次出栈。所以入栈的时候,思路很简单,注意到要将int类型转为Integer类型,我们使用了new Integer(int);当需要出栈的时候,我们用API提供的方法while(stack1.isEmpty())来将所有栈1的元素压入栈2中,然后将栈2弹出就可以。这里又涉及到将Integer的类型转为int类型的方法Integer.intValue();实现代码如下:

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(new Integer(node));
    }
    
    public int pop() {
    if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop().intValue();
    }
}
编辑于 2015-08-24 21:26:48 回复(10)
Javascript 用来展示思路尤其方便。

但是要考虑 pop() 时两个栈为空的处理呀。。 js 是默认返回 undefined ,其他静态语言比如 C++ 我记得会运行时异常吧,没见到有几个处理的。
var inStack = [],
    outStack = [];
function push(node) {
    // write code here
    inStack.push(node);
}
function pop() {
    // write code here
    if (!outStack.length) {
        while (inStack.length) {
            outStack.push(inStack.pop());
        }
    }
    return outStack.pop();
}

编辑于 2017-09-21 14:37:40 回复(0)
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        //等待栈2出完后才能继续入栈不然,不然就会占据栈顶
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int t=stack2.top();
        stack2.pop();
        return t;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

编辑于 2016-07-05 16:51:46 回复(0)
C++:
void push(int node) 
{
  stack1.push(node);
}
int pop()
{
  if(stack2.empty())
{
  while(!stack1.empty())
  {
      stack2.push(stack1.top());
      stack1.pop();
  }
}
 int result=stack2.top();
 stack2.pop();
 return result;  
}
编辑于 2015-07-29 09:42:31 回复(3)
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        # write code here
        if len(self.stack1) == 0:
            while len(self.stack2):
                self.stack1.append(self.stack2.pop())
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if not len(self.stack2) == 0:
            return self.stack2.pop()
        else:
            while len(self.stack1) > 1:
                self.stack2.append(self.stack1.pop())
            return self.stack1.pop()

入队时,判断stack1是否为空,如不为空,将元素压入stack1;如为空,先将stack2元素倒回stack1,再将新元素压入stack1

出队时,判断stack2是否为空,如不为空,则直接弹出顶元素;如为空,则将stack1的元素逐个“倒入”stack2,把stack1最后一个元素弹出并出队。

发表于 2017-08-31 15:53:01 回复(0)

python solution:

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr=[]
    def push(self, node):
  
        self.arr.append(node)
    def pop(self):
    
        return self.arr.pop(0)
编辑于 2017-10-01 20:27:22 回复(5)
//栈的特点:后进先出。队列的特点:先进先出。所以在push方面是一样的,在pop方面需要一个stac//k来做辅助,可以想象成从一杯中把水倒到另一杯中。 import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.add(node);
    }

    public int pop() {
        if(stack2.size()==0){
            while (stack1.size()!=0){
                stack2.push(stack1.pop());//stack1的第一个元素在stack2的末尾
            }
            return stack2.pop();
        }else {//因为stack1的size是在改变的所以当stack2中有元素时需要放到stack1的末尾先输出
            stack1.push(stack2.pop());
            return stack1.pop();
        }

    }
} 


发表于 2017-02-10 14:39:37 回复(0)
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

发表于 2018-08-23 11:26:57 回复(1)
1、如果s2不为空,则返回顶部数据,
2、如果s2为空,s1不为空,则将s1的数据复制到s2后,返回s2顶部数据
3、如果s1也为空,则抛出异常
老铁们,看看我的答案吧
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() throws Exception {
        if (!stack2.isEmpty()){
            return stack2.pop();
        }else if (!stack1.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }else{
            throw new Exception("the queue is empty");
        }
    }
}

编辑于 2018-03-25 00:00:16 回复(0)
//补一个js版本

var stack1 = [], stack2 = [];
function push(node)
{
    // write code here
    stack1.push(node);
}
function pop()
{
    // write code here
    if(stack2.length === 0){
        while(stack1.length !== 0){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}
module.exports = {
    push : push,
    pop : pop
};

发表于 2017-03-24 14:50:13 回复(0)
#Python   感觉讨论组里都是java啊
#无力吐槽了,感觉后台好傻逼,刚开始用随便取了两个变量名,说是越界啥子的,
#后来改成stack1,stack2就过了

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if len(self.stack2) != 0:
            return self.stack2.pop()
        while len(self.stack1) !=0:
            self.stack2.append(self.stack1.pop())

        return self.stack2.pop()

编辑于 2016-11-01 19:44:55 回复(0)
Q:自己想测试这种代码的话,输入该怎么测试?!
发表于 2016-10-21 15:21:25 回复(1)
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        int len = stack1.size();
        for(int i = 0;i < len - 1;i++)  //有一种错误写法,for(int i = 0;i < stack1.size();i++)
        {
            stack2.push(stack1.pop());
        }
        int result = stack1.pop();
        while(!stack2.isEmpty())
        {
            stack1.push(stack2.pop());
        }
        return result;
    }
}
栈是只能进出栈都在栈顶,而队列是队尾进队,队头出队。所以很明显,直接用栈是不行的。
然后进队列是在队尾,而栈进栈也可以看做是栈尾。所以很明显,进队列操作和进栈操作是一样的,所以只需要使用一个栈就行了,这里我们假设使用stack1。
所以接下来我们只要考虑如何使用两个栈使得出队操作是输出栈头部元素。输出头部元素,我们必须将除了第一个进栈的元素外的其他元素全部出栈,比如进栈操作12345,必须将2345出栈。我们很容易想到将2345存在另一个栈中( stack2.push(stack1.pop()) ),此时stack2顺序是5432。然后将1出栈赋值给一个变量(result = stack1.pop()),这个变量就是return的值。然后再讲stack2全部出栈赋值给stack1,此时stack1中元素就为2345( stack1.push(stack2.pop()) )。

但是这里最容易出错的地方:其实是循环,一开始我使用的是for(int i = 0;i < stack1.size();i++),发现答案是错误的。因为stack1.pop()之后,satck1.size()也发生了变化。导致执行了2次循环后就满足条件了。因此,在stack1出栈操作之前,使用一个变量存储stack1的初始长度。
发表于 2016-08-19 11:32:08 回复(1)
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
        
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
            stack2.push(stack1.top());
             stack1.pop();
        }
        }
          int ret = stack2.top();
            stack2.pop();
            return ret;
         
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
发表于 2016-06-23 22:04:15 回复(0)

问题信息

难度:
1271条回答 113845浏览

热门推荐

通过挑战的用户

查看代码