Implement Queue from Scratch

The problem, simply

Build your own queue. A queue is a waiting line: the first one in is the first one out.

It must support:

• enqueue(x): x joins at the back.
• dequeue(): the one at the front leaves, and you give it back.
• peek(): look at the front without removing it.
• isEmpty() and size().

Every action should take the same small amount of time, however long the line gets.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use an array. New kids go in the next free box at the end. When the front kid leaves, take arr[0] and shift every other kid one box to the left.

1. Keep count, the number of kids.
2. Enqueue: write into arr[count], then add one to count.
3. Dequeue: save arr[0], copy arr[1..count-1] one step left, subtract one from count.

class ShiftQueue {
    private final int[] arr;
    private int count = 0;

    ShiftQueue(int capacity) { arr = new int[capacity]; }

    void enqueue(int x) {
        if (count == arr.length) throw new RuntimeException("queue overflow");
        arr[count++] = x;                  // join at the back
    }

    int dequeue() {
        if (count == 0) throw new RuntimeException("queue underflow");
        int val = arr[0];
        for (int i = 1; i < count; i++) {  // everyone steps forward
            arr[i - 1] = arr[i];
        }
        count--;
        return val;
    }

    int peek() {
        if (count == 0) throw new RuntimeException("queue is empty");
        return arr[0];
    }

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

    int size() { return count; }
}

How long it takes: enqueue is O(1), but every dequeue shifts the whole line, O(n). Extra room: the fixed array, O(capacity).

Way 2: the clever way

Nobody steps forward. Make the line a chain of boxes, a linked list, and keep two tags:

• front sits on the box that leaves next.
• rear sits on the last box, where new boxes are hooked on.

1. Enqueue: make a new box. If the line is empty, both tags go to it. Otherwise hook it after rear, then move rear to it.
2. Dequeue: take the value in front, then move front to the next box. If front became null, the line is empty, so set rear to null too.
3. Keep a counter for size().

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

    private Node front, rear;          // leave here, join there
    private int count;

    void enqueue(int x) {
        Node box = new Node(x);
        if (rear == null) {
            front = rear = box;        // first kid in an empty line
        } else {
            rear.next = box;           // hook on at the back
            rear = box;
        }
        count++;
    }

    int dequeue() {
        if (front == null) throw new RuntimeException("queue underflow");
        int val = front.val;
        front = front.next;            // slide the front tag
        if (front == null) rear = null; // line is empty again
        count--;
        return val;
    }

    int peek() {
        if (front == null) throw new RuntimeException("queue is empty");
        return front.val;
    }

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

    int size() { return count; }
}

How long it takes: every action moves at most two tags, O(1). Extra room: one box per waiting value, O(n).

Watch out for

• Enqueue at the head and dequeue at the tail does not work well with a singly linked list. Removing the tail needs the box before it, which takes a walk. Join at the tail, leave at the head.
• An array where front only moves forward and never wraps around wastes the boxes at the start. That leads to a "full" queue that is mostly empty. The fix is a circular array.
• Peek or dequeue on an empty line must not crash with a null pointer.

What interviewers ask next

• Can you do it with an array and still get O(1) dequeue? Yes, with a circular array. Let front and rear wrap around with % capacity and keep a count to tell full from empty.
• What about a queue that can grow without limit using an array? Use a circular array and double it when full. When copying, unroll it so front lands at index 0.
• How does Java do it? ArrayDeque is a growable circular array. LinkedList also works as a Queue but uses more memory per item.
• Build a queue from two stacks. Push into one stack, pop from the other, and pour the first into the second only when the second is empty.
• Where are queues used? Breadth first search, printer jobs, task schedulers, and message buffers between programs.

Remember this

Grown-up words: the waiting line is a queue, first in first out is FIFO, joining is enqueue, leaving is dequeue, the chain of boxes is a singly linked list, and the two name tags are the head and tail pointers.