Cormen Edition 3 Exercise 10.1 Question 3 (Page No. 235)

Question

ENQUEUE(Q, x)
1     Q[Q.tail] = x
2     if Q.tail == Q.length
3     Q.tail = 1
4     else Q.tail = Q.tail + 1


DEQUEUE(Q)
1      x = Q[Q.head]
2      if Q.head == Q.length
3      Q.head = 1
4      else Q.head = Q.head + 1
5      return x

illustrate the result of each operation in the sequence ENQUEUE(Q,4),ENQUEUE(Q,1),ENQUEUE(Q,3),DEQUEUE(Q),ENQUEUE(Q,8),DEQUEUE(Q) on an initially empty queue $Q$ stored in array $Q[1...6]$.

Answer 1

Given initially empty queue Q stored in array Q[1..6], index starts from 1

Initial values--> tail=1 for insertion at the rear end of array

                           head=1 for deletion from the front end of array

 

Operations:                           RESULT

OP1: ENQUEUE(Q,4)-->       x=4  Q: 4,__,__,__,__,__

                                               Q.tail=2 , from step 4 of ENQUEUE(Q,X)

 

OP2: ENQUEUE(Q,1)-->       x=1  Q: 4,1,__,__,__,__

                                               Q.tail=3 , from step 4 of ENQUEUE(Q,X)

 

OP3: ENQUEUE(Q,3)-->       x=3  Q: 4,1,3,__,__,__

                                               Q.tail=4 , from step 4 of ENQUEUE(Q,X)

 

OP4: DEQUEUE(Q)-->         x=4   Q: __,1,3,__,__,__

                                              Q.head=2, from step 4 of DEQUEUE(Q)

                                              return x=4  from step 5 of DEQUEUE(Q)

 

OP5: ENQUEUE(Q,8)-->       x=8  Q: __,1,3,8,__,__

                                               Q.tail=5 , from step 4 of ENQUEUE(Q,X)

 

OP6: DEQUEUE(Q)-->         x=1   Q: __,__,3,__,__,__

                                              Q.head=3, from step 4 of DEQUEUE(Q)

                                              return x=1  from step 5 of DEQUEUE(Q)