Kata: Stack and Queue

Table of contents

Problem Statement

Part 1: Implement a Stack

A Last-In-First-Out (LIFO) data structure with:

• push(value) — add to top, O(1)
• pop() — remove from top, O(1)
• peek() — view top without removing, O(1)
• isEmpty() — check if empty

Part 2: Implement a Queue

A First-In-First-Out (FIFO) data structure with:

• enqueue(value) — add to back, O(1)
• dequeue() — remove from front, O(1)
• peek() — view front without removing, O(1)
• isEmpty() — check if empty

Part 3 (Challenge): Queue from Two Stacks

Implement a queue using only two stacks. This is a classic interview question.

Concepts

Stacks and queues are the simplest abstract data types after arrays. They restrict access patterns to enforce ordering guarantees:

• Stack: Think of a stack of plates — you can only add/remove from the top
• Queue: Think of a line at a store — first in, first out

Python: collections.deque provides O(1) operations at both ends, making it ideal for both stacks and queues. See Python Core Concepts.

PHP: SPL provides SplStack and SplQueue. See PHP Core Concepts.

Boilerplate

TypeScript

// stack.ts
class Stack<T> {
  private items: T[] = [];

  push(value: T): void { /* TODO */ }
  pop(): T | undefined { /* TODO */ return undefined; }
  peek(): T | undefined { /* TODO */ return undefined; }
  isEmpty(): boolean { /* TODO */ return true; }
  get size(): number { return this.items.length; }
}

// queue.ts
class Queue<T> {
  // TODO: choose your internal representation
  enqueue(value: T): void { /* TODO */ }
  dequeue(): T | undefined { /* TODO */ return undefined; }
  peek(): T | undefined { /* TODO */ return undefined; }
  isEmpty(): boolean { /* TODO */ return true; }
}

// queue-from-stacks.ts
class QueueFromStacks<T> {
  private inbox: Stack<T> = new Stack();
  private outbox: Stack<T> = new Stack();

  enqueue(value: T): void { /* TODO */ }
  dequeue(): T | undefined { /* TODO */ return undefined; }
}

Hints

Solution

TypeScript

class Stack<T> {
  private items: T[] = [];

  push(value: T): void {
    this.items.push(value);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  get size(): number {
    return this.items.length;
  }
}

class Queue<T> {
  private items: Map<number, T> = new Map();
  private head = 0;
  private tail = 0;

  enqueue(value: T): void {
    this.items.set(this.tail, value);
    this.tail++;
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    const value = this.items.get(this.head);
    this.items.delete(this.head);
    this.head++;
    return value;
  }

  peek(): T | undefined {
    return this.items.get(this.head);
  }

  isEmpty(): boolean {
    return this.head === this.tail;
  }

  get size(): number {
    return this.tail - this.head;
  }
}

class QueueFromStacks<T> {
  private inbox = new Stack<T>();
  private outbox = new Stack<T>();

  enqueue(value: T): void {
    this.inbox.push(value);
  }

  dequeue(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) {
        this.outbox.push(this.inbox.pop()!);
      }
    }
    return this.outbox.pop();
  }

  peek(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) {
        this.outbox.push(this.inbox.pop()!);
      }
    }
    return this.outbox.peek();
  }

  isEmpty(): boolean {
    return this.inbox.isEmpty() && this.outbox.isEmpty();
  }
}

Complexity Analysis

Stack

Queue (Map-based)

Queue from Two Stacks

Each element is moved between stacks at most once, so amortized cost is O(1).

Cross-Language Notes

Python: Use collections.deque for production queues — it provides O(1) append() and popleft(). Python lists work fine as stacks (append/pop) but are O(n) for pop(0). See Python Core Concepts.

PHP: SplStack extends SplDoublyLinkedList with LIFO iteration, and SplQueue with FIFO. Both provide O(1) operations. See PHP Core Concepts.

JavaScript: The QueueFromStacks pattern is used in real systems — for example, some message queues use dual-buffer designs inspired by this approach.