剑指Offer-用两个栈实现队列

2017/3/10 posted in  算法-数据结构  

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

解决思路

栈是后进先出,而队列是先进先出,在pop的过程上是相反的。所以我们要解决的核心问题就是这样。
Stack1用来push数据,这样,最先进入的元素就成为了Stack1的栈底元素。当我们需要出队时,需要找到第一个进入stack1的元素,于是,我们分别将stack1的元素出栈,压入stack2,这时,stack2中的栈顶元素,就是最开始我们插入栈中的元素,也就是我们要pop的元素。
所以,就有了如下的规则:

  • push操作:压入stack1中;
  • pop操作:如果stack2中有元素,则返回stack2的栈顶元素;若stack2为空,则依次将stack1中的元素出栈,压入stack2中,返回stack2的栈顶元素。

代码如下:

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(stack2.size() > 0 ){
            return stack2.pop();
        }
        
        while(stack1.size() > 0 ){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}