1、用两个栈实现队列

栈的特点就是先进后出，类似于手枪弹匣一样；队列的特点是先进先出，类似于水管；
要用两个栈实现队列的功能，需要熟练的应用栈和队列两种数据结构。
思路：

  • 使用两个栈，其中一个栈只用来执行push操作，另一个栈用来pop操作；
  • 第一个栈正常进栈，当需要出栈的时候，把第一个栈的数据全部弹出到第二个栈；
  • 此时第二个栈存放的是第一个栈数据的倒序，队列放出消息，就是二栈弹出数据；
  • 一栈正常数据进栈，若要消息出队列，调用deleteHead()方法；

实现代码如下：

  1. /**
  2.  * 用两个栈实现队列
  3.  */
  4. class CQueue_day01 {
  5.     Deque<Integer> stack1;
  6.     Deque<Integer> stack2;
  8.     public CQueue_day01() {
  9.         stack1 = new LinkedList<>();
  10.         stack2 = new LinkedList<>();
  11.     }
  13.     //栈一压栈
  14.     public void appendTail(int value) {
  15.         stack1.push(value);
  16.     }
  18.     //出队列，栈二出栈
  19.     public int deleteHead() {
  20.         // 如果第二个栈为空
  21.         if (stack2.isEmpty()) {
  22.             while (!stack1.isEmpty()) {
  23.                 stack2.push(stack1.pop());
  24.             }
  25.         }
  26.         //stack2为空，stack1为空，返回-1
  27.         if (stack2.isEmpty()) {
  28.             return -1;
  29.         } 
  30.         //stack2不为空，直接弹出，弹出的就是队列出来的数据
  31.         else {
  32.             int deleteItem = stack2.pop();
  33.             return deleteItem;
  34.         }
  35.     }
  36. }