PadhaikoAll subjects

Past exam question: 2064 Jestha, Q2

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Queues

Question

What are the applications of queue? Write an algorithm for linear queue where both the head and tail pointer vary. Trace your algorithm with an example.

Solution

Applications of Queue:

  1. CPU & Disk Scheduling: Ready queue for FCFS and Round-Robin scheduling.
  2. I/O & Print Spooling: Print jobs and keyboard/network packet buffers served in FIFO order.
  3. Graph & Tree Algorithms: Breadth-First Search (BFS), level-order tree traversal, and Kahn's topological sort.

Linear Queue Algorithm (front / Head and rear / Tail Vary): Initially front = 0, rear = -1 on Q[0..MAX-1]:

Algorithm ENQUEUE(Q, val):
1. If rear == MAX - 1:
       Print "Queue Overflow"; Return
2. rear = rear + 1
3. Q[rear] = val

Algorithm DEQUEUE(Q):
1. If front > rear:
       Print "Queue Underflow"; Return -1
2. val = Q[front]
3. front = front + 1
4. Return val

Trace Example (MAX = 4): Start: front = 0, rear = -1.

  1. ENQUEUE(10) rear=0, Q=[10], front=0.
  2. ENQUEUE(20) rear=1, Q=[10, 20], front=0.
  3. DEQUEUE() returns 10, front=1, rear=1 (Q[1]=20 active).
  4. ENQUEUE(30) rear=2, Q=[-, 20, 30], front=1.
Answer:

Queues power OS/CPU scheduling, print/packet buffering, and BFS/level-order traversals. In a varying-head/tail linear queue, ENQUEUE increments rear (rear == MAX - 1 checks full) and DEQUEUE increments front (front > rear checks empty).

All past exam questions for Data Structure and Algorithms