Past exam question: 2066 Jestha (Back), Q2
Open in the Padhaiko appQuestion
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:
- False Overflow: Once
rear == MAX - 1, insertions fail even when earlierdequeue()calls have emptied slots0..front-1. - 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):
- Empty condition:
front == -1 - Full condition:
(rear + 1) % MAX == front
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 valTrace Example (MAX = 3):
CQ_ENQUEUE(10)front=0, rear=0,Q=[10, -, -]CQ_ENQUEUE(20)front=0, rear=1,Q=[10, 20, -]CQ_ENQUEUE(30)front=0, rear=2,Q=[10, 20, 30](now(2+1)%3 == 0 == frontFull!)CQ_DEQUEUE()returns10,front = 1, rear = 2CQ_ENQUEUE(40)rear = (2+1)%3 = 0,Q=[40, 20, 30](slot0reused!).
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.