Study Guide

Queues

Computer ScienceΒ· Unit 10: Data types & structuresΒ· 15 min read

1. Core Concepts and FIFO Propertyβ˜…β˜…β˜†β˜†β˜†β± 3 min

πŸ“˜ Definition

Queue

Often denoted

A linear abstract data type that follows the First In First Out (FIFO) ordering principle for insertion and deletion. Elements are added at one end (rear/back) and removed from the opposite end (front).

Example:

A queue of customers at a checkout: the first customer to join is the first to be served.

All standard queue operations are restricted to the two ends. Unlike linked lists or arrays, you cannot access or modify elements in the middle of a queue by default. This restriction ensures the FIFO property is maintained.

πŸ“ Worked Example

A queue starts empty. Trace the state of the queue after the following operations: Enqueue(10), Enqueue(25), Dequeue(), Enqueue(30), Peek(), Dequeue(). List the final queue contents and the value returned by Peek().

  1. 1

    Step 1: Initial state: empty queue, front and rear both null. After Enqueue(10):

  2. 2

    Queue = , front = 10, rear = 10

  3. 3

    Step 2: After Enqueue(25): 25 added to rear.

  4. 4

    Queue = , front = 10, rear = 25

  5. 5

    Step 3: After Dequeue(): 10 is removed from front.

  6. 6

    Queue = , front = 25, rear = 25

  7. 7

    Step 4: After Enqueue(30): 30 added to rear.

  8. 8

    Queue = , front = 25, rear = 30

  9. 9

    Step 5: Peek() returns the value of the front element (25) with no change to the queue.

  10. 10

    Step 6: After Dequeue(): 25 is removed from front. Final state:

  11. 11

    Queue = , front = 30, rear = 30

Exam tip:

Always explicitly label which end is front and which is rear when tracing operations: swapping these is the most common mistake in CIE exams.

2. Standard Queue Operationsβ˜…β˜…β˜†β˜†β˜†β± 4 min

All valid queue implementations support the following core operations, each with an expected time complexity of :

  • enqueue(item): Add a new element to the rear of the queue

  • dequeue(): Remove and return the element from the front of the queue

  • peek() / front(): Return the value of the front element without removing it

  • isEmpty(): Return True if the queue has no elements, else False

  • isFull(): Return True if the queue has no remaining space (fixed-size implementations only)

βœ“ Quick check

Test your understanding of core operation properties:

  1. Which operation adds a new element to a queue?

    • Dequeue

    • Enqueue

    • Peek

    • isEmpty

    Reveal answer
    Enqueue β€”

    Correct: Enqueue adds to the rear, dequeue removes from the front.

  2. What is the time complexity of a correctly implemented enqueue operation?

    Reveal answer
    $O(1)$ β€”

    Correct: Enqueue only modifies the rear pointer, so it runs in constant time.

πŸ“ Worked Example

Write pseudocode for the isEmpty() operation for a fixed-size array-based queue that tracks frontIndex and rearIndex.

  1. 1

    For this common implementation, the queue is empty when frontIndex equals rearIndex, because no elements are between the two pointers.

  2. 2

    The resulting pseudocode for the function is:

  3. 3
    \begin{algorithm} \FUNCTION{isEmpty()}{} \RETURN frontIndex = rearIndex \ENDFUNCTION \end{algorithm}
  4. 4

    If your implementation tracks a separate elementCount variable, the equivalent pseudocode is RETURN elementCount = 0. Both are acceptable in CIE exams as long as logic is consistent.

3. Common Queue Implementationsβ˜…β˜…β˜…β˜†β˜†β± 5 min

Methods compared

Queues are most commonly implemented with two underlying structures, compared below:

Fixed Array-based Queue

Uses a contiguous array to store queue elements, with integer pointers for front and rear indices.

+ Pros: Simple to implement, constant time access to front/rear

βˆ’ Cons: Fixed maximum size, wasted memory in naive linear implementations

Linked-list-based Queue

Uses linked list nodes, with separate pointers to the front and rear nodes of the list.

+ Pros: Dynamic size, no pre-allocated wasted memory

βˆ’ Cons: Higher memory overhead from node pointers

The circular queue is an improved fixed array implementation that solves the problem of empty slots left at the start of the array after deletions. The rear index wraps around to the start of the array once it reaches the end, reusing empty slots.

πŸ“ Worked Example

A circular queue has a fixed size of 5, with array indices 0 to 4. Current state: frontIndex = 2, rearIndex = 4. Find the new indices after Enqueue(10) and Dequeue().

  1. 1

    Step 1: Current state: all positions after index 4 are at the start of the array (circular wrap-around).

  2. 2

    Step 2: Enqueue(10) adds the new element to index 0, so rearIndex increments from 4 to 0. frontIndex remains 2.

  3. 3

    Step 3: Dequeue() removes the element at front index 2, so frontIndex increments from 2 to 3. rearIndex remains 0.

  4. 4

    Final state: frontIndex = 3, rearIndex = 0

Exam tip:

CIE often asks for circular queue implementations: remember that one slot is always left empty to distinguish between the full and empty states.

4. Applications of Queuesβ˜…β˜…β˜†β˜†β˜†β± 3 min

  • Process scheduling: Operating systems use queues to order waiting CPU processes by arrival time

  • Printer spooling: Print jobs are queued so the first job sent is the first job printed

  • Breadth-First Search (BFS): Graph traversal uses a queue to track nodes to visit next

  • Data buffering: Queues handle asynchronous data transfer (e.g. video streaming, IO buffers)

πŸ“ Worked Example

Explain why a queue is the ideal data structure for printer spooling with multiple users.

  1. 1

    Printer spooling requires that documents are printed in the exact order they are received by the printer.

  2. 2

    The FIFO property of queues matches this requirement: the first document added to the queue is the first document processed and printed.

  3. 3

    New documents can be added to the rear of the queue while the printer processes jobs from the front, eliminating conflicts between multiple users.

5. Common Pitfalls

Wrong move:

Swapping front and rear ends for enqueue/dequeue operations

Why:

Learners often confuse which end supports which operation, breaking the FIFO property

Correct move:

Enqueue adds to the rear, dequeue removes from the front, always following FIFO order

Wrong move:

Forgetting that circular queues leave one slot empty to distinguish full/empty states

Why:

If all slots are filled, front = rear which matches the empty queue condition, causing logical errors

Correct move:

Leave one empty slot for circular arrays, or track element count separately to avoid ambiguity

Wrong move:

Claiming enqueue/dequeue are for correctly implemented queues

Why:

Learners often assume elements must be shifted in array implementations, which is only true for naive non-pointer implementations

Correct move:

All correctly implemented queues with front/rear pointers have time complexity for core operations

Wrong move:

Using a queue for depth-first graph traversal

Why:

Common confusion between BFS and DFS requirements

Correct move:

Use a queue for BFS, and a stack for DFS, matching their FIFO/LIFO properties respectively

6. Quick Reference Cheatsheet

Feature

Detail

Ordering Principle

First In First Out (FIFO)

Insertion End

Rear / Back

Deletion End

Front

Core Operations

Enqueue, Dequeue, Peek, isEmpty, isFull

Core Op Time Complexity

Common Implementations

Fixed array, circular array, linked list

Key Applications

BFS, CPU scheduling, printer spooling, buffering

7. Frequently Asked

What is the key difference between a stack and a queue?

Stacks follow LIFO (Last In First Out) order, where the most recently added item is removed first. Queues follow FIFO (First In First Out) order, where the oldest added item is removed first.

When this came up on past exams

AI-estimated based on syllabus patterns β€” cross-check with official past papers for accuracy. Use only as revision-focus signals.

  • 2022 Β· 1

    Queue implementation question

  • 2023 Β· 2

    Queue application description

Going deeper

What's Next

Queues are a fundamental linear data structure used across many advanced topics in the CIE 9618 syllabus, including graph algorithms, operating system scheduling, and system design. Exam questions on queue implementation and application appear regularly in both Paper 1 and Paper 2, so mastering core concepts and common implementation edge cases is critical for good marks. Next, you can explore related data structures and advanced topics that rely on queues.