Redirected
edited by
9,481 views
4 votes
4 votes

A circular array based queue $q$ is capable of holding $7$ elements. After execution of the following code, find the element at index $'1'$, if the array is initially empty and array has indices from $0$ to $6$.

  for (x=1; x<=6; x++) 
      q.enqueue (x); 
  for (x=1; x<=3; x++)
 {    q.dequeue ();
      q.enqueue (q.dequeue ()); 
 }

Assume enqueue & dequeue are circular queue operations for insertion and deletion respectively.

edited by

4 Answers

Best answer
14 votes
14 votes

Enqueue adding element from Rear and dequeue deleting element from Front 

initially queue is 

for( x=1;x<=6;x++)

q.enqueue(x);  // elements are added from Rear., rear = rear+1

Queue look like 

for x= 1 

q.dequeue();    // delete element from Front i.e  1 from index 0

q.enqueue(q.dequeue());  // delete element from Front, i.e 2 from index 1, add 2 from Rear, i.e at index6

Queue look like 

Repeat the process for x = 2 and x=3 

Finally Queue will be 

So element at the Index1 is 6 

selected by
2 votes
2 votes
In the first loop, array elements 1 to 6 are inserted from arr [0] to arr [5] position.. arr [6] remains empty...

for the second loop..

it is run only three times

for i=1, q.dequeue is performed.. it deletes arr [0] position & 1 is removed... now q.enqueue (q.dequeue), this statement first performs delete operation from front position which will return 2 and then insert this in rear position which is arr [6]..  2 is inserted at arr [6] position...

similarly for I=2.. first 3 is deleted.. and again 4 is deleted and inserted at arr [0] position...

and for i=3.. first 5 is deleted.. and again 6 is deleted and inserted at arr [1] position...

so element at index 1 is 6...
0 votes
0 votes

> We know that in an circular array implementation of Queue initially pointers Front and Rear will point to same location

> Overflow Condition: If (Rear+1) mod n = Front

> Underflow Condition: If Front and Rear pointers were pointing to same location (This also indicates that the queue is empty)

1. Initially our array will look like this

Pointer F,R            
Index 0 1 2 3 4 5 6
Value              

After running 

for(x=1;x<=6;x++)

q.enqueue(x);

we will end up with an array looking like this 

Pointer F           R
Index 0 1 2 3 4 5 6
Value   1 2 3 4 5 6

 Please note that Rear pointer will be incremented before insertion 

2.) Now the below steps will occur 

for (int k = 1; k <= 3; k++) { q.dequeue(); q.enqueue(q.dequeue());  } 

I will show you the state of our array and the pointer after each iteration please bear with me

i.) x=1; first dequeue() is called so the pointer 'F' will be incremented and the value pointed by it will be returned, alas we have no use for the value returned by it so simply increment the pointer when ever you see this statement  

Pointer   F         R
Index 0 1 2 3 4 5 6
Value   1 2 3 4 5 6

ii.) q.enqueue(q.dequeue());

    Now this is where things get really interesting we are enqueing the dequeued value, let me break it down for you

    a.) Increment the 'F' pointer pop the value pointed by it

Pointer     F       R
Index 0 1 2 3 4 5 6
Value   1 2 3 4 5 6

pop will return 2

    b.) Increment the 'R' pointer and insert the value popped previously

Pointer R   F        
Index 0 1 2 3 4 5 6
Value 2 1 2 3 4 5 6

At the end of running for x=2 our array will look like

Pointer   R     F    
Index 0 1 2 3 4 5 6
Value 2 4 2 3 4 5 6

At the end of running for x=3 our array will look like

Pointer     R       F
Index 0 1 2 3 4 5 6
Value 2 4 6 3 4 5 6

This where our little program will stop.

We are asked for the value stored in the index 1 and that will be 4.  

Related questions

0 votes
0 votes
1 answer
1
manvi_agarwal asked Jul 29, 2018
314 views
https://gateoverflow.in/?qa=blob&qa_blobid=10936115150698131975
3 votes
3 votes
3 answers
2
Ibtisam Sayyad asked Jan 12, 2018
7,864 views
What are the minimum enqueue and dequeue operations needed to perform pop operation for a stack which is implemented with two queues if there are already 10 elements in t...
2 votes
2 votes
1 answer
4