Implementing the Stack

A Stack is an Abstract Data Type (ADT). We can build it using:

1. Array: Fast access, cache-friendly.
2. Linked List: Dynamic size, no resizing cost.

1. Core Operations

All Stack 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.
• IsEmpty(): Check if the stack is empty.

2. Java & Go: The Right Way

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class StackDemo {
  public void demo() {
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(10); // O(1)
    stack.push(20);

    int top = stack.peek(); // 20
    int popped = stack.pop(); // 20

    boolean isEmpty = stack.isEmpty(); // false
  }
}

Go

type Stack []int

func (s *Stack) Push(v int) {
  *s = append(*s, v) // O(1) amortized
}

func (s *Stack) Pop() int {
  if len(*s) == 0 { return -1 }
  index := len(*s) - 1
  val := (*s)[index]
  *s = (*s)[:index] // Shrink slice
  return val
}

func (s *Stack) Peek() int {
  if len(*s) == 0 { return -1 }
  return (*s)[len(*s)-1]
}

[!NOTE] Java Specific: > [!WARNING] Do NOT use java.util.Stack. It is a legacy class (synchronized, slow). Use java.util.ArrayDeque instead.

[!NOTE] Go Specific: In Go, we simply use a Slice.

---

3. The MinStack Problem (O(1) Min)

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

Naive Approach: Scan the stack for min? O(N). Too slow.

Optimal Approach: Use Two Stacks.

1. Main Stack: Stores actual values.
2. Min Stack: Stores the minimum value seen so far.

Interactive: MinStack Visualizer

Push values and watch how the MinStack updates.

Main Stack

Min Stack

Current Min: None

4. Implementation Details

Java

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();
  }
}

Go

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

func (this *MinStack) Push(val int) {
  this.stack = append(this.stack, val)
  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]
  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]
}

Practice: Backspace String Compare

Apply your knowledge of LIFO for string processing:

[!TIP] Vault: Backspace String Compare