Min Stack

描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

    分析

用两个栈,一个是真实的栈,另一个作为辅助栈,辅助栈每次 push 时,会把新元素跟当前栈顶元素进行比较,存入二者中较小的那个。

举个例子,对于序列 18, 19, 21, 15, 17, 两个栈依次push进去的元素是这样的:

  • 真实栈,18, 19, 21, 15, 17
  • 辅助栈,18, 18, 18, 15, 15

    具体过程是这样的,对于 18, 辅助栈是空的,直接push进去,当遇到19时,此时栈顶元素是18,二者中18较小,就把18插入,此时辅助栈中就有了两个18,当遇到21时,以此类推,还是插入18,遇到15时,栈顶元素是18,15较小,就把15压入,此时辅助栈中有3个18,1个15,当遇到17时,栈顶元素是15,二者中15是较小值,于是插入15,结束。

代码

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/stack-and-queue/stack/min-stack.html