放两个表情： 🐣🥚

1 用两个栈实现队列

像汉诺塔问题一般, 利用两个栈结构来颠倒栈内数据的顺序.

  1. class CQueue {
  2.     Stack<Integer> in;
  3.     Stack<Integer> out;
  4.     public CQueue() {
  5.         in = new Stack<>();
  6.         out = new Stack<>();
  7.     }
  9.     public void appendTail(int value) {
  10.         in.push(value);
  11.     }
  13.     public int deleteHead() {
  14.         if (out.size() < 1) {
  15.             if (in.size() < 1) {
  16.                 return -1;
  17.             }
  18.             in2Out();
  19.         }
  20.         return out.pop();
  21.     }
  23.     private void in2Out() {
  24.         while(!in.isEmpty()) {
  25.             out.push(in.pop());
  26.         }
  27.     }
  28. }

2 自定义栈结构 (带有min()方法)

思路: 自定义节点结构Node (val, min, next) 三个参数, val 表示当前值就不说了, min 这个参数就是典型的空间换时间了, 在每个节点上都存了一份目前为止的最小值, next 最重要的就这个参数, 它才保证了形成栈的结构, 它存放的是自身前一个进来的节点, 即上一个被压入栈中的元素.

  1. class MinStack {
  3.     private Node topNode;
  5.     /** initialize your data structure here. */
  6.     public MinStack() { }
  8.     public void push(int x) {
  9.         if (topNode == null) 
  10.             topNode = new Node(x, x, null);
  11.         else 
  12.             topNode = new Node(x, Math.min(x, topNode.val), topNode);
  13.     }
  15.     public void pop() {
  16.         topNode = topNode.next;
  17.     }
  19.     public int top() {
  20.         return topNode.val;
  21.     }
  23.     public int min() {
  24.         return topNode.min;
  25.     }
  27.     // next 就相当于被压入栈底的旧节点
  28.     private class Node {
  29.         int val, min;
  30.         Node next;
  31.         public Node(int val, int min, Node next) {
  32.             this.val = val;
  33.             this.min = min;
  34.             this.next = next;
  35.         }
  36.     }
  37. }