Queue — In-Depth Understanding

Definition:

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. This means that the first element added to the queue will be the first one to be removed.

Key Concepts:

• Front: Points to the element that will be removed first.
• Rear: Points to the position where the new element will be inserted.

Real-Life Analogy:

At a bus stop queue:

• People join at the rear (new additions).
• The person who arrives first leaves first when the bus comes (front).

2. Core Queue Operations

2.1 Insertion (Enqueue):

• Always done at the rear.
• Edge Case: If rear == size - 1 → Overflow.
• Special Case: If the queue is empty (front == -1), then set front = 0 before inserting the first element.

2.2 Deletion (Dequeue):

• Always done from the front.
• Edge Case: If front == -1 or front > rear → Underflow.
• Post-deletion: If front > rear, reset both to -1 indicating an empty queue.

2.3 Display:

• Loop from front to rear.
• Handles partial queues with gaps from deletions.