Past exam question: 2064 Jestha, Q2
Open in the Padhaiko appQuestion
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:
- CPU & Disk Scheduling: Ready queue for FCFS and Round-Robin scheduling.
- I/O & Print Spooling: Print jobs and keyboard/network packet buffers served in FIFO order.
- 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 valTrace Example (MAX = 4): Start: front = 0, rear = -1.
ENQUEUE(10)rear=0, Q=[10],front=0.ENQUEUE(20)rear=1, Q=[10, 20],front=0.DEQUEUE()returns10,front=1, rear=1(Q[1]=20active).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).