剑指offer系列之五：用两个栈实现队列

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

题目描述

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

栈的特点是先进后出，而队列的特点是先进先出。题目中提到使用两个栈实现队列，好像有戏。现在问题是如何把栈的出栈和入栈与队列的入队和出队联系起来？因为现在只有栈，所以在实现的队列中，只能先往栈中添加元素，这点比较好理解；那么出队呢，由于先进去的元素被压在栈底，而如果是队列的话，必须是栈底的那个元素先出队。现在可以使用第二个栈，思路是把原先第一个栈中的元素出栈，并压入第二个栈中，观察第二个栈，就可以发现：在第二个栈中的元素顺序与正常队列出队的顺序是一致的了。所以这样，问题就解决了。

下面是在牛客AC的代码：

package com.rhwayfun.offer;import java.util.Stack;public class CreateQueueWithStacks {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {//首先入队的元素先放入stack1中stack1.push(node);}public int pop() {//当需要弹出栈顶元素的时候，先把stack1中的元素全部弹出到stack2中//这样，当stack1中没有元素的时候，直接从stack2中弹出栈顶元素即可if(stack2.size() <= 0){while(stack1.size() > 0){stack2.push(stack1.pop());}}//异常处理if(stack2.size() == 0){try {throw new Exception("empty queue");} catch (Exception e) {e.printStackTrace();}}return stack2.pop();}public static void main(String[] args) {CreateQueueWithStacks cq = new CreateQueueWithStacks();cq.push(1);cq.push(2);cq.push(3);System.out.println(cq.pop());System.out.println(cq.pop());System.out.println(cq.pop());cq.push(4);System.out.println(cq.pop());}
}