Queue Data Structure

What is a queue?

A queue is an abstract data type that holds an ordered, linear sequence of items and follows First‑In, First‑Out (FIFO) semantics.

Real‑life example

• A line at a ticket counter: people join at the rear and are served at the front.

• Cars waiting at a toll booth: the first car to arrive is the first to pass through.

Key characteristics

• FIFO structure: the element that goes in first is the one that comes out first.

• You can only enqueue (add) at the rear, and only dequeue (remove) from the front.

• To implement efficiently in a fixed‑size array, you often maintain front and rear pointers and use wrap‑around (circular buffer) when you reach the end of the array.

What are the operations of a queue?

The primary queue operations are:

• enqueue(data) – adds an element to the rear of the queue

• dequeue() – removes and returns the element at the front of the queue

• peek() (or front()) – returns (but does not remove) the front element

• is_empty() – returns true if the queue has no elements

• is_full() – returns true if the queue has reached its maximum capacity (for fixed‑size implementations)

How does a queue work?

1. Initialisation

   • Start with an empty sequence and set both front and rear pointers to –1 (or 0, depending on your convention).

2. Enqueue (Adding)

   • Increment the rear pointer (wrapping around if at the end of the array).

   • Place the new element at the position indicated by rear.

   • If this is the first element, also set front = rear.

3. Dequeue (Removing)

   • Read the element at the front pointer.

   • Increment the front pointer (wrapping around if necessary).

   • If after removal the queue becomes empty, reset both front and rear to the “empty” value.

4. Peek

   • Simply return the element at front without modifying any pointers.

5. Wrap‑around (Circular Queue)

   • When rear (or front) reaches the end of the array, it wraps to index 0.

   • Ensures constant‑time operations without shifting all elements.