A queue is a linear data structure that follows first in, first out (FIFO): the first element added is the first element removed. Enqueue adds an element at the rear of the queue, while dequeue removes the element at the front.
How a Queue Works
A queue is an abstract data type (ADT) because its behaviour and permitted operations are defined independently of its implementation. It has two important positions:
- The front holds the next element to be removed.
- The rear is where the next element is added.
Consider an initially empty queue. The following operations occur:
- Enqueue A:
[A] - Enqueue B:
[A, B] - Enqueue C:
[A, B, C] - Dequeue: A is removed, leaving
[B, C] - Enqueue D:
[B, C, D]
A must be removed before B and C because it entered the queue first. Unlike a stack, a queue does not remove the most recently added element.
| Operation | Effect |
|---|---|
| Enqueue | Adds an element at the rear |
| Dequeue | Removes and usually returns the element at the front |
| Peek or front | Returns the front element without removing it |
| isEmpty | Checks whether the queue contains no elements |
Attempting to dequeue from an empty queue causes underflow. In a fixed-size queue, attempting to enqueue when no storage remains causes overflow. A circular queue can reuse array positions freed by earlier dequeue operations, improving storage efficiency.
Exam Technique
For IB Computer Science subtopic B2.2 Data structures, be prepared to define FIFO and trace a sequence of queue operations. Show the queue after every operation and label the front and rear when appropriate. A common misconception is that dequeue removes the newest element; that is stack behaviour (LIFO), not queue behaviour.
