13.8 Implement Queue

13.8.1 Problem Metadata

  • Platform: Interview Prep
  • Problem ID: Queue Design
  • Difficulty: Easy
  • URL: N/A
  • Tags:
  • Techniques: Array, Linked List, Stack

13.8.2 Description

Implement a queue with operations enqueue, dequeue, peek, and isEmpty. Explore multiple representations.

13.8.3 Examples

MyQueue queue = new MyQueue(3);
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue(); // 1
queue.enqueue(3);
queue.peek(); // 2

13.8.4 Constraints

  • Assume integers, bounded or unbounded based on implementation

13.8.5 Solution 1 - Circular Array

13.8.5.1 Walkthrough

Use a fixed-size array with head, tail, and count. Enqueue writes at tail then wraps around; dequeue reads from head. This avoids shifting elements.

13.8.5.2 Analysis

  • Time Complexity: O(1)
  • Space Complexity: O(capacity)

13.8.5.3 Implementation Steps

  1. Initialize head = 0, tail = 0, count = 0.
  2. enqueue(x): if count == capacity throw overflow; assign data[tail] = x, tail = (tail + 1) % capacity, increment count.
  3. dequeue(): if empty throw, read data[head], advance head, decrement count.
  4. peek() returns data[head].

13.8.5.4 Code - Java

class ArrayQueue {
    private final int[] data;
    private int head = 0;
    private int tail = 0;
    private int count = 0;

    public ArrayQueue(int capacity) {
        this.data = new int[capacity];
    }

    public void enqueue(int x) {
        if (count == data.length) {
            throw new IllegalStateException("Queue full");
        }
        data[tail] = x;
        tail = (tail + 1) % data.length;
        count++;
    }

    public int dequeue() {
        if (count == 0) {
            throw new NoSuchElementException();
        }
        int value = data[head];
        head = (head + 1) % data.length;
        count--;
        return value;
    }

    public int peek() {
        if (count == 0) {
            throw new NoSuchElementException();
        }
        return data[head];
    }

    public boolean isEmpty() {
        return count == 0;
    }
}

13.8.6 Solution 2 - Linked List

13.8.6.1 Walkthrough

Maintain front and rear pointers of a singly linked lc-list. Enqueue appends at the tail; dequeue removes from the head.

13.8.6.2 Analysis

  • Time Complexity: O(1)
  • Space Complexity: O(n)

13.8.6.3 Implementation Steps

  1. Each node holds value plus next.
  2. enqueue(x): create node, append at rear, update pointers.
  3. dequeue(): remove front, adjusting rear when queue becomes empty.

13.8.6.4 Code - Java

class LinkedQueue {
    private static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    private Node front;
    private Node rear;

    public void enqueue(int x) {
        Node node = new Node(x);
        if (rear == null) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
    }

    public int dequeue() {
        if (front == null) {
            throw new NoSuchElementException();
        }
        int value = front.val;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return value;
    }

    public int peek() {
        if (front == null) throw new NoSuchElementException();
        return front.val;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

13.8.7 Solution 3 - Two Stacks

13.8.7.1 Walkthrough

Use two stacks in and out. Enqueue pushes onto in. Dequeue/peek pop from out, reloading it from in when empty by moving all elements to reverse order.

Note: This approach is identical to LeetCode 232: Implement Queue using Stacks, which provides a detailed walkthrough with visual examples and amortized complexity analysis.

13.8.7.2 Analysis

  • Time Complexity: Amortized O(1)
  • Space Complexity: O(n)

13.8.7.3 Implementation Steps

  1. enqueue(x): push onto in.
  2. dequeue() / peek(): if out empty, move all elements from in to out, then pop/peek.
  3. isEmpty(): true when in and out are empty.

13.8.7.4 Code - Java

class QueueWithStacks {
    private final Stack<Integer> in = new Stack<>();
    private final Stack<Integer> out = new Stack<>();

    public void enqueue(int x) {
        in.push(x);
    }

    public int dequeue() {
        shift();
        return out.pop();
    }

    public int peek() {
        shift();
        return out.peek();
    }

    public boolean isEmpty() {
        return in.isEmpty() && out.isEmpty();
    }

    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }
}