Design Stack

Overview

Design stack: implement a stack with given operations, typically push, pop, top, and often getMin (or getMax), all O(1) amortized or worst-case. Use an array (push/pop at end) or a linked list (top = head). For getMin, use an auxiliary Min Stack or store (value, minSoFar) in each node.

When to Use

• Stack + getMin/getMax — min stack or (val, min) pairs.
• Stack with O(1) everything — array or linked list; no extra ops.
• Foundation for Min Stack, Queue using Stacks.

How It Works

Storage: array (stack.push/pop) or linked list (insert/remove at head). getMin: either a second stack that stays non-increasing, or each element stores (value, minWhenPushed). getMax: same with non-decreasing stack or (value, maxWhenPushed).

Example 1: Basic Stack (Array)

class MyStack {
  private arr: number[] = [];
  push(x: number): void { this.arr.push(x); }
  pop(): number { return this.arr.pop()!; }
  top(): number { return this.arr[this.arr.length - 1]; }
  empty(): boolean { return this.arr.length === 0; }
}

All O(1).

Example 2: Stack with getMin (Auxiliary Stack)

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];
  push(val: number): void {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1])
      this.minStack.push(val);
  }
  pop(): void {
    const x = this.stack.pop()!;
    if (this.minStack[this.minStack.length - 1] === x) this.minStack.pop();
  }
  top(): number { return this.stack[this.stack.length - 1]; }
  getMin(): number { return this.minStack[this.minStack.length - 1]; }
}

See Min Stack for details.

Example 3: Stack with getMin (Store Pair)

Each node stores (value, minSoFar). Push: minSoFar = min(val, top.minSoFar or val). getMin = top.minSoFar. No second stack; O(1) extra space per element.

class MinStackPair {
  private stack: [number, number][] = [];
  push(val: number): void {
    const min = this.stack.length === 0 ? val : Math.min(this.stack[this.stack.length - 1][1], val);
    this.stack.push([val, min]);
  }
  pop(): void { this.stack.pop(); }
  top(): number { return this.stack[this.stack.length - 1][0]; }
  getMin(): number { return this.stack[this.stack.length - 1][1]; }
}

Example 4: Stack with Linked List

Top = head. Push: new node, next = head, head = new. Pop: val = head.val, head = head.next, return val. O(1) per op; no array resize.

class Node { constructor(public val: number, public next: Node | null) {} }
class StackLL {
  private head: Node | null = null;
  push(x: number): void { this.head = new Node(x, this.head); }
  pop(): number { const v = this.head!.val; this.head = this.head!.next; return v; }
  top(): number { return this.head!.val; }
  empty(): boolean { return this.head === null; }
}

Example 5: Edge Cases and Variants

• Empty pop/top: document or throw; or return -1.
• getMax: same as getMin with max stack (non-decreasing) or (val, maxSoFar).
• Capacity: array stack can grow; linked list has no fixed cap. Specify if problem asks for fixed size.

Summary

• Design stack: array or linked list for push/pop/top; getMin via Min Stack or (value, minSoFar) pairs. See Stack Basics.