Stack which, in addition to push and pop, also has a

function min which returns the minimum element. Push, pop and min

operate in 0(1) time

To solve this we use 2 stack

- superStack
- stackWithMin

superStack behaves like a normal stack and stackWithMin keeps track of minimum values.

Below is code snippet for the class with generic implementation.

public class StackWithMin<T> where T : IComparable { private Stack<T> superStack; private Stack<T> stackWithMin; public StackWithMin() { this.superStack = new Stack<T>(); this.stackWithMin = new Stack<T>(); } public T Pop() { if (this.superStack.Count <= 0) throw new InvalidOperationException("Stack Empty."); T lastPopedElement = this.superStack.Pop(); T element = this.stackWithMin.Peek(); if (element.CompareTo(lastPopedElement) == 0) { this.stackWithMin.Pop(); } return lastPopedElement; } public void Push(T element) { if (this.superStack.Count == 0) { this.stackWithMin.Push(element); this.superStack.Push(element); return; } if (element.CompareTo(this.Min()) <= 0) { this.stackWithMin.Push(element); } this.superStack.Push(element); } public T Min() { if (this.superStack.Count <= 0) throw new InvalidOperationException("Stack Empty."); return this.stackWithMin.Peek(); } }