Queues

Definition

• A Queue is a linear ADT following FIFO (First-In-First-Out) — like a line of people, first person in is first served

Core Operations (all O(1) with proper implementation)

• enqueue(x) — add element to the rear
• dequeue() — remove and return element from the front
• front()/peek() — view front element
• isEmpty()

Types of Queues

• Simple Queue — basic FIFO
• Circular Queue — rear wraps around to reuse freed front space, avoiding wasted array slots
• Priority Queue — elements served by priority, not arrival order (typically implemented via a Heap — links directly to Heap Sort topic)
• Deque (Double-Ended Queue) — insertion/deletion allowed at both ends

Key Applications (frequently tested)

• BFS (Breadth-First Search) in graph traversal — uses a queue (vs DFS's stack)
• CPU/Process scheduling in operating systems (Round Robin uses a circular queue)
• Print/task spooling, buffering (data streams, IO)
• Level-order traversal of trees

Exam Angle

Pair this directly with Stacks in comparison answers: Stack = LIFO → DFS, recursion; Queue = FIFO → BFS, scheduling. Priority Queue's Heap-based implementation is a common cross-topic exam link (see Heap Sort page).

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: ADT Specification of Queue

2016, Paper I, Q6(a) (8 marks) — Write Abstract Data Types (ADT) of Stack and Queue. Include the specifications of Add, Delete, IsEmpty, IsFull functions along with their respective functions.

Model answer (Queue half):

ADT Queue (FIFO — First In First Out):

• Objects: a finite ordered list of elements with two ends — "front" (for removal) and "rear" (for insertion).
• Add — Enqueue(item): inserts item at the rear. Precondition: queue not full.
• Delete — Dequeue(): removes and returns the item at the front. Precondition: queue not empty.
• IsEmpty(): returns true if front == rear (no elements), else false.
• IsFull(): returns true if rear has reached MAXSIZE (or, in a circular queue, if the next rear position equals front), else false.
• Peek(): returns the front element without removing it.

Exam angle: FPSC explicitly names "Implementation of Stacks and Queues using ADTs" as a syllabus topic — this is the direct hit for that line item, and examiners want the pre/postcondition checks (queue not full/not empty) stated explicitly, not just the one-line description of what Enqueue/Dequeue "does."

📝 Exam Practice: Constant-Time Access to Both Ends

2018, Paper I, Q5(d) (5 marks) — How would you modify a linked-list based queue so that first and last node can be accessed in a constant time regardless of data nodes in the queue?

Model answer: Maintain two separate pointers as part of the queue's structure at all times — a front pointer (always pointing to the first/head node, used for dequeue) and a rear/tail pointer (always pointing to the last node, used for enqueue) — instead of only keeping a single head pointer and traversing the whole list to find the last node on every insertion.

Enqueue (insert at rear):
    create newNode
    if queue non-empty: rear->next = newNode
    rear = newNode
    if queue was empty: front = newNode
    // O(1)

Dequeue (remove from front):
    save temp = front
    front = front->next
    delete temp
    if queue becomes empty: rear = nullptr
    // O(1)

Key reasoning points: with both front and rear explicitly maintained and updated on every operation, both ends are directly reachable in O(1) — avoiding the O(n) traversal that a single-head-pointer implementation would need to locate the last node.

📝 Exam Practice: Priority Queue Application

2025, Paper I, Q10 (1 mark) — What is the correct data structure for implementing Huffman algorithm?

• A. Priority queue ✓
• B. Linked list
• C. Binary Tree
• D. None of these

MCQ Trap: it's tempting to answer "Binary Tree" since Huffman coding builds a binary tree — but the algorithm's core repeated operation is "extract the two lowest-frequency nodes and merge them," which is exactly what a min-priority queue (typically a min-heap) is built to do efficiently. The tree is the output; the priority queue is the working data structure during construction — a distinction worth stating explicitly if asked to justify the choice.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q6(a) · 8 marks (queue part)

Q. Write the Abstract Data Type of Queue, with the specifications of Add, Delete, IsEmpty and IsFull.

Ans.

ADT Queue (FIFO)
  Data: ordered items with front and rear; capacity MAX
  Operations:
    Create()     : make an empty queue (front = rear = -1)
    Add(x)       : precondition: not full;  post: x is at the rear   (Enqueue)
    Delete()     : precondition: not empty; post: front item removed and returned (Dequeue)
    IsEmpty()    : true if no items
    IsFull()     : true if rear = MAX - 1 (for a linear array queue)

• A circular queue reuses freed slots: rear = (rear + 1) % MAX, full when (rear + 1) % MAX == front.

2018 · Paper-I · Q5(d) · 5 marks

Q. How would you modify a linked-list-based queue so that the first and last nodes can be accessed in constant time regardless of the number of data nodes?

Ans.

• Keep two pointers, front and rear, in the queue structure, pointing to the first and last nodes.
• Enqueue at the rear: rear->next = newNode; rear = newNode; (if the queue was empty, set both pointers to the new node).
• Dequeue from the front: temp = front; front = front->next; delete temp; (if front becomes null, set rear to null).
• Without the rear pointer, adding at the end needs a walk through the whole list (O(n)). With both pointers, enqueue, dequeue and access to both ends are O(1).