Stacks and Queues

Queue Enqueue/Dequeue

Enqueue values at the back and dequeue them from the front in first-in, first-out order.

Algorithm

Basic Implementation

Basic.java 
import java.util.*;

public class Basic {
    static String render(List<Integer> values) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < values.size(); i++) {
            if (i > 0) out.append(" -> ");
            out.append(values.get(i));
        }
        return out.toString();
    }
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int value : new int[] {10, 20, 30}) queue.add(value);
        List<Integer> removed = new ArrayList<>();
        while (!queue.isEmpty()) removed.add(queue.remove());
        System.out.println(render(removed));
    }
}

The queue keeps the oldest value at the front and adds new values at the back.

Step 1 - Enqueue 10, 20, 30

New values join at the back. The oldest value, 10, stays at the front.

Queue after three enqueues: front 10, then 20, then back 30.nextnext10front2030back

Step 2 - Dequeue removes 10

Removing from the front returns 10 and makes 20 the new front.

After one dequeue: removed is 10; front moves to 20.next10removed20front30back

Complexity

  • Time: O(1) per operation with a real queue
  • Space: O(n)

Implementation notes

  • Java declares the queue as Queue<Integer> and backs it with new ArrayDeque<>(), so operations use the queue interface while storage is an array-backed deque.
  • The enhanced for loop reads primitive values from new int[] {10, 20, 30}; each queue.add(value) appends at the back and boxes the int into an Integer for the generic container. These small boxed values may come from the Integer cache.
  • Dequeue uses while (!queue.isEmpty()) removed.add(queue.remove()). remove() takes from the front and would throw on an empty queue, so the guard is the checked empty behavior in this implementation.
  • The replay-visible FIFO states move from [10, 20, 30] to [20, 30] and then [], while removed grows to [10, 20, 30]. The ArrayDeque, ArrayList, and StringBuilder output are normal JVM heap objects managed while referenced.
front The front is the oldest value still waiting in the queue.
FIFO A queue removes values in first-in, first-out order.