search
Log In
0 votes
126 views
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]$.

in Algorithms
edited by
126 views

1 Answer

0 votes

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)

                                               

Related questions

0 votes
0 answers
1
0 votes
1 answer
2
93 views
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
asked Jun 28, 2019 in Algorithms akash.dinkar12 93 views
0 votes
1 answer
3
157 views
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double ended queue) allows insertion and deletion at both ends. Write four $O(1)$ time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
asked Jun 28, 2019 in Algorithms akash.dinkar12 157 views
0 votes
1 answer
4
172 views
Explain how to implement two stacks in one array $A[1...n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$.The $PUSH$ and $POP$ operations should run in $O(1)$ time.
asked Jun 28, 2019 in Algorithms akash.dinkar12 172 views
...