Implementing the Stack

[!NOTE] This module explores the core principles of Stack Operations and the Min Stack problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

A Stack is an Abstract Data Type (ADT) that follows LIFO (Last In, First Out). Core operations must be O(1):

Push(val): Add val to the top.
Pop(): Remove and return the top element.
Peek(): Return the top element without removing it.

Challenge (Min Stack): Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

2. Interactive Analysis

Push values and watch how the MinStack updates. Note that MinStack only records values smaller than or equal to the current minimum.

Main Stack

Min Stack

Current Min: None

3. Intuition: Two Stacks

Naive Approach: Scanning the stack for the minimum is O(N). Optimization: We need to “cache” the minimums.

Imagine a stack of plates. On each plate, we write a number. On a sticky note attached to that plate, we write “The smallest number from this plate downwards”. When we remove a plate, we remove its sticky note too. The new top plate reveals the previous minimum.

We implement this “sticky note” concept using a second stack, minStack.

4. Implementation

Java

// Note: Use Deque/ArrayDeque, NOT Stack (legacy)
class MinStack {
  private Deque<Integer> stack = new ArrayDeque<>();
  private Deque<Integer> minStack = new ArrayDeque<>();

  public void push(int val) {
    stack.push(val);
    // Only push to minStack if new value is <= current min
    if (minStack.isEmpty() || val <= minStack.peek()) {
      minStack.push(val);
    }
  }

  public void pop() {
    int val = stack.pop();
    // Only pop minStack if we removed the min value
    if (val == minStack.peek()) {
      minStack.pop();
    }
  }

  public int getMin() {
    return minStack.peek();
  }
}

type MinStack struct {
  stack    []int
  minStack []int
}

func (this *MinStack) Push(val int) {
  this.stack = append(this.stack, val)
  // Push to minStack if empty or smaller/equal
  if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
    this.minStack = append(this.minStack, val)
  }
}

func (this *MinStack) Pop() {
  val := this.stack[len(this.stack)-1]
  this.stack = this.stack[:len(this.stack)-1]
  // Pop from minStack if values match
  if val == this.minStack[len(this.minStack)-1] {
    this.minStack = this.minStack[:len(this.minStack)-1]
  }
}

func (this *MinStack) GetMin() int {
  return this.minStack[len(this.minStack)-1]
}

5. Complexity Analysis

Strategy	Time	Space	Notes
Two Stacks	O(1)	O(N)	Every operation is constant time. Space stores redundant mins.

Stack Operations & Min Stack