重要1.栈实现队列

image.png
push栈导数据到pop栈中有两个条件：①pop栈为空②push栈一次全部导入。

  1. public static class TwoStacksQueue {
  2.         public Stack<Integer> stackPush;
  3.         public Stack<Integer> stackPop;
  5.         public TwoStacksQueue() {
  6.             stackPush = new Stack<Integer>();
  7.             stackPop = new Stack<Integer>();
  8.         }
  10.         // push栈向pop栈倒入数据
  11.         private void pushToPop() {
  12.             if(!stackPop.empty()){
  13.                 stackPop.clear();//清空stackPop
  14.             }
  15.             if (stackPop.empty()) {
  16.                 while (!stackPush.empty()) {
  17.                     stackPop.push(stackPush.pop());
  18.                 }
  19.             }
  20.         }
  22.         public void add(int pushInt) {
  23.             stackPush.push(pushInt);
  24.             pushToPop();
  25.         }
  27.         public int poll() {
  28.             if (stackPop.empty() && stackPush.empty()) {
  29.                 throw new RuntimeException("Queue is empty!");
  30.             }
  31.             pushToPop();
  32.             return stackPop.pop();
  33.         }
  35.         public int peek() {
  36.             if (stackPop.empty() && stackPush.empty()) {
  37.                 throw new RuntimeException("Queue is empty!");
  38.             }
  39.             pushToPop();
  40.             return stackPop.peek();
  41.         }
  42.     }

2.队列实现栈

image.png
先将data队列中出队四个数到help队列中，然后把data的最后一个数出队列；其次让help和data互换，继续上面的操作。
栈中加入数字时就在data中入队列即可。

  1. public static class TwoQueueStack<T> {
  2.         public Queue<T> queue;
  3.         public Queue<T> help;
  5.         public TwoQueueStack() {
  6.             queue = new LinkedList<>();
  7.             help = new LinkedList<>();
  8.         }
  10.         public void push(T value) {
  11.             queue.offer(value);
  12.         }
  14.         public T poll() {
  15.             while (queue.size() > 1) {
  16.                 help.offer(queue.poll());
  17.             }
  18.             T ans = queue.poll();
  19.             Queue<T> tmp = queue;
  20.             queue = help;
  21.             help = tmp;
  22.             return ans;
  23.         }
  25.         public T peek() {
  26.             while (queue.size() > 1) {
  27.                 help.offer(queue.poll());
  28.             }
  29.             T ans = queue.poll();
  30.             help.offer(ans);
  31.             Queue<T> tmp = queue;
  32.             queue = help;
  33.             help = tmp;
  34.             return ans;
  35.         }
  37.         public boolean isEmpty() {
  38.             return queue.isEmpty();
  39.         }
  41.     }