PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q2

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Queues

Question

What are the demerits of simple linear queue? Write an algorithm to insert and remove data items for circular queue with the condition for queue full and empty. Trace your algorithm with an example.

Solution

Demerits of Simple Linear Queue:

  1. False Overflow: Once rear == MAX - 1, insertions fail even when earlier dequeue() calls have emptied slots 0..front-1.
  2. Shifting Cost: Shifting all items to index 0 after every dequeue() degrades performance from to .

Circular Queue Algorithms (Q[0..MAX-1], initially front = rear = -1):

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

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

Trace Example (MAX = 3):

  1. CQ_ENQUEUE(10) front=0, rear=0, Q=[10, -, -]
  2. CQ_ENQUEUE(20) front=0, rear=1, Q=[10, 20, -]
  3. CQ_ENQUEUE(30) front=0, rear=2, Q=[10, 20, 30] (now (2+1)%3 == 0 == front Full!)
  4. CQ_DEQUEUE() returns 10, front = 1, rear = 2
  5. CQ_ENQUEUE(40) rear = (2+1)%3 = 0, Q=[40, 20, 30] (slot 0 reused!).
Answer:

Simple linear queues suffer false overflow and shifting; a circular queue reuses slots via (index + 1) % MAX using empty check front == -1 and full check (rear + 1) % MAX == front.

All past exam questions for Data Structure and Algorithms