剑指offer 用两个栈实现队列 Java

题目

题目描述

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

---

题解

首先想到栈是FILO，队列是FIFO，那么就很容易想到队列出队POP操作的实现方法为：
  1.我们进行入队操作时，直接将元素Push进stack1中；
  2.此时stack1中的元素都是倒着排放的，第一个进入的元素在栈底，而我们想要获取的元素正是栈底的元素，所以我们将stack1中的元素全部转移至stack2中，此时stack2栈顶的元素就是我们所需要的队列队尾的元素，此时直接stack2.pop()；
  3.我们经过第一步的操作之后的得到的stack2中的元素此时全部为有序，意思是我们想要继续获取队列队尾的元素时，stack2中的堆顶的元素就是我们队列的队尾元素，此时接着stack2.pop()；
  4.若想要继续获取队列队尾元素时，发现stack2中元素为空，此时重复2步骤，将stack1中的元素转移至stack2中，接着获取stack2的堆顶元素即可；

---

代码

import java.util.*;

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 fal;
        if(stack2.isEmpty()){
            int size = stack1.size();
            int tmp;
            while(size-- >0){
                tmp = stack1.pop();
                stack2.push(tmp);
            }
        }
        fal = stack2.pop();
        return fal;
    }
}