Queue

Picture a line at a ticket counter: whoever joined the line first gets served first, and new people join at the back. Nobody can jump the line or leave from the middle. That's exactly the rule a queue follows.

FIFO: First In, First Out

This is the opposite of a stack's LIFO rule. A stack removes the most recently added element first; a queue removes the least recently added element first, since it's been waiting the longest.

Array representation

A queue is commonly implemented with an array plus two variables: FRONT, marking the position of the element that will leave next, and REAR, marking the position where the next inserted element will go.

Removal always happens at FRONT (10 leaves first), and insertion always happens just past REAR (the next element would go at index 4). By convention, similar to a stack's TOP = -1, an empty queue is usually represented with FRONT = -1.

ENQUEUE: inserting an element

To insert at the rear:

1. Check whether the queue is full. If it is, print OVERFLOW and stop.
2. Move REAR forward.
3. Insert the item at Q[REAR].

ENQUEUE(Q, item)
 
If REAR == MAX - 1
    Print "OVERFLOW"
Else
    If FRONT == -1
        FRONT = 0
    REAR = REAR + 1
    Q[REAR] = item

The FRONT == -1 check exists because on the very first insertion into an empty queue, FRONT also needs to move to index 0, there's no element at the front yet for it to already be pointing at.

DEQUEUE: removing an element

To remove from the front:

1. Check whether the queue is empty. If it is, return UNDERFLOW and stop.
2. Read Q[FRONT].
3. Move FRONT forward.
4. Return the removed item.

DEQUEUE(Q)
 
If FRONT == -1
    return UNDERFLOW
Else
    item = Q[FRONT]
    FRONT = FRONT + 1
    return item

A common simple implementation resets both FRONT and REAR back to -1 once the last element is removed, so the queue correctly reports itself as empty again rather than leaving stale index values behind.

The problem with a simple array-based queue

Suppose a queue of capacity 5 fills up completely, then three elements are dequeued:

Indices 0, 1, and 2 are now empty (dimmed), freed up by the dequeues. But REAR is already sitting at index 4, the last index in the array. The simple ENQUEUE algorithm above checks REAR == MAX - 1 and prints OVERFLOW, refusing to insert, even though three cells at the front are sitting unused.

Queue complexity

Like a stack, every core queue operation only touches one end, so each runs in constant time:

Applications

FIFO ordering shows up wherever "first come, first served" is the natural rule:

• Task scheduling: operating systems queue processes or print jobs so they run in the order they arrived.
• Breadth-first search: graph and tree traversal algorithms that explore level by level use a queue to keep track of what to visit next, in the order nodes were discovered.
• Buffering: data arriving faster than it can be processed (network packets, keystrokes, I/O requests) gets queued so it's handled in the order it arrived rather than dropped or reordered.

Quick recall

• A queue allows insertion only at the rear and removal only at the front, giving FIFO ordering: first in, first out.
• The array-based implementation uses FRONT (next to leave) and REAR (last inserted), with FRONT = -1 marking an empty queue.
• ENQUEUE checks for overflow (REAR == MAX - 1) before inserting; DEQUEUE checks for underflow (FRONT == -1) before removing.
• A plain array-based queue wastes the space freed up by dequeues at the front, since REAR can hit the array's end while earlier indices sit empty, this is what motivates the circular queue.
• Every queue operation is O(1).