Queue

FIFO (First-In, First-Out) data structure

Interactive Queue Operations

Drag elements to enqueue at the rear, or click the front element to dequeue.

Drag elements to enqueue (add to rear)

Queue (FIFO)Size: 0 / 8

Queue is empty

Drag an element here to enqueue

Operation History

No operations yet

Java Implementation

Array-Based Queue

Queue implementation using an array with front and rear pointers

public class ArrayQueue<T> {
    private T[] array;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.array = (T[]) new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    public void enqueue(T item) {
        if (size >= capacity) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T item = array[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return array[front];
    }

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

    public int size() {
        return size;
    }
}

Time: O(1) for all operationsSpace: O(n) where n is capacity

Implementation Comparison

Aspect	Array-Based	LinkedList-Based
Memory	Fixed size, may waste space	Dynamic, node overhead per element
Enqueue/Dequeue	O(1) with circular array	O(1) with front/rear pointers
Overflow	Can overflow if array is full	No overflow (until memory exhausted)
Wrap-around	Needs modulo arithmetic	Not applicable
Use case	Known max size, circular buffer	Unknown size, simple implementation

Priority Queue

A Priority Queue removes elements based on priority, not arrival order. See how it differs from a regular queue in this ER triage simulation.

Hospital ER Triage Scenario

In an emergency room, patients are not served in arrival order. Instead, those with higher severity are treated first. This is a Priority Queue!

Compare: Regular Queue (FIFO - first come, first served) vs Priority Queue (highest priority first)

Add Patient

Patient Name

Severity (1-10)

Quick add:

Regular Queue (FIFO)

First come, first served

Queue is empty

Priority Queue

Highest severity first

Queue is empty

Severity Levels

Critical (8-10)

Urgent (5-7)

Moderate (3-4)

Minor (1-2)

Key Insight

Notice how the Regular Queue serves patients in arrival order, while the Priority Queue always serves the most critical patient first, regardless of when they arrived.

In Java, use PriorityQueue with a customComparator to control the priority ordering.

Common Pitfalls

⚠️ Dequeue from Empty Queue

Calling dequeue() without checking if queue is empty

Queue<Integer> queue = new LinkedList<>();
// queue.remove(); // Throws NoSuchElementException!

// Correct way:
if (!queue.isEmpty()) {
    int value = queue.remove();
}
// Or use poll() which returns null instead of throwing
Integer value = queue.poll(); // null if empty

Prevention: Always check isEmpty() or use poll() instead of remove()

⚠️ Confusing FIFO with LIFO

Expecting stack behavior from a queue

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
// queue.poll() returns 1, not 3!
// For LIFO, use Stack or Deque as stack

Prevention: Remember: Queue = FIFO (first in, first out)

⚠️ Priority Queue Assumptions

Assuming PriorityQueue maintains insertion order

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
// pq.poll() returns 1 (smallest), not 3 (first inserted)

// For FIFO with priority, need custom comparator
// that considers both priority AND arrival time

Prevention: PriorityQueue orders by natural ordering or comparator, not insertion order

← Stack Comparison →