A queue works like a line at a shop: the first person to join is the first to be served. Queues keep things fair and in order. This lesson explains queue rules, operations and the circular queue.
FIFO
A queue follows FIFO: First In, First Out. Items are added at the rear (back) and removed from the front.
Operations
- enqueue(item): add an item to the rear.
- dequeue(): remove and return the item at the front.
- peek() / front(): look at the front item without removing it.
- isEmpty(): true if there are no items.
- isFull(): true if a fixed-size queue has no space.
Example:
enqueue(A) // [A]
enqueue(B) // [A, B]
enqueue(C) // [A, B, C] front = A, rear = C
dequeue() // returns A, queue is [B, C]
Dequeuing from an empty queue is underflow; enqueuing to a full queue is overflow.
Linear array implementation
Keep an array with two index variables, front and rear.
Q = new array[5]
front = 0
rear = -1
size = 0
PROCEDURE enqueue(item)
if size = 5 then
output "Queue full"
else
rear = rear + 1
Q[rear] = item
size = size + 1
end if
END PROCEDURE
FUNCTION dequeue()
if size = 0 then
output "Queue empty"
else
item = Q[front]
front = front + 1
size = size - 1
return item
end if
END FUNCTION
Problem: as items are dequeued, the front moves right and the space at the start of the array is wasted. Eventually the rear reaches the end even though the queue is not full.
Circular queue
A circular queue fixes this by wrapping the indexes around using the remainder operator:
rear = (rear + 1) mod 5
front = (front + 1) mod 5
The array is treated as a ring, so freed space at the start is reused. The size counter (or a spare slot) distinguishes a full queue from an empty one.
Linked-list implementation
Use a linked list with pointers to both the head (front) and tail (rear). Enqueue adds at the tail and dequeue removes from the head. Both are O(1) and the queue grows as needed.
Variations
- Priority queue: items leave in order of priority, not arrival; an emergency patient is seen before a minor injury.
- Deque (double-ended queue): allows adding and removing at both ends.
Check your understanding
What does FIFO mean?
- First In, First Out
- Fast In, Fast Out
- Final In, First Out
- First In, Fixed Out
Answer: First In, First Out. The oldest item is removed first.
After enqueue(1), enqueue(2), enqueue(3), dequeue(), what is at the front?
- 1
- 2
- 3
- Nothing
Answer: 2. The 1 was removed from the front.
Why use a circular queue?
- To reuse freed space at the start of the array
- To make the queue a stack
- To sort items
- To reduce items
Answer: To reuse freed space at the start of the array. Indexes wrap around using mod.
Which queue type serves items by importance instead of arrival time?
- Priority queue
- Circular queue
- Linear queue
- Stack
Answer: Priority queue. Higher-priority items leave first.
