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

1113个回答

添加回答

就借助栈先入后出的特点,进行操作就好

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

    int pop() {
        int data = 0;
        if(stack2.size() <= 0)
        {
            while(stack1.size() > 0)
            {
                data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        if(stack2.size() == 0)
            throw "";
        data = stack2.top();
        stack2.pop();
        return data;
    }
发表于 2018-03-13 19:54:49 回复(0)
更多回答
推荐
class Solution 
   查看全部
编辑于 2015-08-18 23:15:03 回复(42)
这是左程云的《程序员代码面试指南》的答案:
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 回复(35)
思路:
  • 栈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 回复(10)
//每次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)
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 回复(4)
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 回复(9)
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 回复(2)
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)

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 回复(4)
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)
# -*- 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)
//栈的特点:后进先出。队列的特点:先进先出。所以在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)
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)
/**
* 用两个栈来实现队列的push()和pop()操作
* 注意这里的队列的特性:先进先出,并且,其中的push()操作为添加元素到队列末尾,pop()操作为弹出队首元素,并且将其删除
* 其中栈的特性为:先进后出
* 算法思想:这里利用了两个栈,来实现队列的操作,由队列和栈的特性可以知道,可以利用一个栈来作为过渡使用,即:
* 当向队列中插入数据时,实际上将其插入栈stack1中
* 当要从队列中弹出队首元素时,就可以将stack1中的元素依次写入到stack2中(由于在stack1中元素的顺序与队列中的正好相反,所以再次反即为正,反反得正)
* 所以这个时候,从栈stack2中弹出的栈顶元素即为队列中的队首元素
*/
Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
    //注意这里不必每次都将stack2清空,因为再后面的逆转回去时,会将栈中的元素pop()掉,这个操作就相当于清空了stack2,stack1也是一样的
    //注意这里是将stack1中的元素逆转(反反得正)
    while(!stack1.isEmpty()){
    stack2.push(stack1.pop());
    }
    //这里将要返回的队首的值取到了
    int getNumber = stack2.pop();
    //在取到对应的队首元素之后,就需要将剩下的元素在返回到原本的栈stack1中去
    while(!stack2.isEmpty()){
    stack1.push(stack2.pop());
    }
    return getNumber;
    }

发表于 2017-03-05 16:30:50 回复(0)
Q:自己想测试这种代码的话,输入该怎么测试?!
发表于 2016-10-21 15:21:25 回复(0)
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)

两个栈,进来的数先push到栈1中,当栈1不为空且栈2为空的时候,将栈1全部pop到栈2中
完成了队列排序。
注意:当栈2还有数据时不能从栈1pop进栈2,等栈2为null时才能将栈1所有的数push到栈2
中。不然会导致顺序混乱。
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.isEmpty()&&stack2.isEmpty()){
           while(!stack1.isEmpty()){
               stack2.push(stack1.pop());
           }
       }
        return stack2.pop();
    }
}






















发表于 2018-06-14 12:33:57 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋