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.