最小栈

实现一个栈，该栈带有出栈，入栈，取最小值 3 个方法。保证这三个方法的时间复杂度都是栈 - 图1。

  1. 设原有的栈叫作栈 A，此时创建一个额外的“备胎”栈 B，用于辅助栈 A。

image.png

  1. 当第 1 个元素进入栈 A 时，让新元素也进入栈 B。这个唯一的元素是栈 A 的当前最小值。

image.png

  1. 之后，每当新元素进入栈 A 时，比较新元素和栈 A 当前最小值的大小，如果小于栈 A 当前最小值，则让新元素进入栈 B，此时栈 B 的栈顶元素就是栈 A 当前最小值。

image.png

  1. 每当栈A有元素出栈时，如果出栈元素是栈 A 当前最小值，则让栈 B 的栈顶元素也出栈。此时栈 B 余下的栈顶元素所指向的，是栈 A 当中原本第 2 小的元素，代替刚才的出栈元素成为栈 A 的当前最小值。（备胎转正。）

image.png

  1. 当调用 getMin 方法时，返回栈 B 的栈顶所存储的值，这也是栈 A 的最小值。

    1. public class MinStack {
    3.  private Stack<Integer> mainStack = new Stack<>();
    4.  private Stack<Integer> minStack = new Stack<>();
    6.  // 入栈
    7.  public void push(int element) {
    8.      mainStack.push(element);
    9.      // 如果辅助栈为空，或者新元素小于或等于辅助栈栈顶元素，则将新元素入栈
    10.      if (minStack.empty() || element <= minStack.peek()) {
    11.          minStack.push(element);
    12.      }
    13.  }
    15.  // 出栈
    16.  public Integer pop() {
    17.      // 如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
    18.      if (mainStack.peek().equals(minStack.peek())) {
    19.          minStack.pop();
    20.      }
    21.      return mainStack.pop();
    22.  }
    24.  // 获取栈的最小元素
    25.  public int getMin() throws Exception {
    26.      if (mainStack.empty()) {
    27.          throw new Exception("stack is empty");
    28.      }
    29.      return minStack.peek();
    30.  }
    32.  public static void main(String[] args) throws Exception {
    33.      MinStack stack = new MinStack();
    34.      stack.push(4);
    35.      stack.push(9);
    36.      stack.push(7);
    37.      stack.push(3);
    38.      stack.push(8);
    39.      stack.push(5);
    40.      System.out.println(stack.getMin());
    41.      stack.pop();
    42.      stack.pop();
    43.      stack.pop();
    44.      System.out.println(stack.getMin());
    45.  }
    46. }

    如何用栈实现队列

    用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。

这里可以使用两个栈来模拟队列操作，假设有栈A，栈B两个栈，我们可以用栈A 模拟入队操作，用栈B模拟出队操作，具体操作流程如下：

  1. 让元素依次插入栈A；
  2. 假设现在需要出栈，将栈A中的元素依次出栈，并按照出栈顺序依次压入栈B；
  3. 出栈时依次从栈B弹出元素；
  4. 有新的元素入栈时，让其继续压入栈A；
  5. 出栈时若栈B不为空，则继续从栈B中弹出元素，若栈B为空，则重复第2步；

  6. ……

    1. public class StackImplQueue {
    3.  private Stack<Integer> stackA = new Stack<>();
    4.  private Stack<Integer> stackB = new Stack<>();
    6.  // 入队
    7.  public void enqueue(int element) {
    8.      stackA.push(element);
    9.  }
    11.  // 出队
    12.  public Integer deQueue() {
    13.      if (stackB.isEmpty()) {
    14.          if (stackA.isEmpty()) {
    15.              return null;
    16.          }
    17.          transfer();
    18.      }
    19.      return stackB.pop();
    20.  }
    22.  // 栈 A 元素移到栈 B
    23.  private void transfer() {
    24.      while (!stackA.isEmpty()) {
    25.          stackB.push(stackA.pop());
    26.      }
    27.  }
    29.  public static void main(String[] args) {
    30.      StackImplQueue stackImplQueue = new StackImplQueue();
    31.      stackImplQueue.enqueue(1);
    32.      stackImplQueue.enqueue(2);
    33.      stackImplQueue.enqueue(3);
    34.      System.out.println(stackImplQueue.deQueue());
    35.      System.out.println(stackImplQueue.deQueue());
    36.      stackImplQueue.enqueue(4);
    37.      System.out.println(stackImplQueue.deQueue());
    38.      System.out.println(stackImplQueue.deQueue());
    39.  }
    40. }