in DS retagged ago by
6,396 views
11 votes
11 votes

Consider the queues $Q_{1}$ containing four elements and $Q_{2}$ containing none (shown as the $\textsf{Initial State}$ in the figure). The only operations allowed on these two queues are $\textsf{Enqueue (Q, element)}$ and $\textsf{Dequeue (Q)}.$ The minimum number of $\textsf{Enqueue}$ operations on $Q_{1}$ required to place the elements of $Q_{1}$ in $Q_{2}$ in reverse order (shown as the $\textsf{Final State}$ in the figure) without using any additional storage is________________.

 

in DS retagged ago by
by
6.4k views

4 Comments

edited by

We should consider Q2 to be an array of size greater than length 4, then only the answer will come.

Step 0: Enqueue 1 in Q2, it is already sorted,

Step 1: Enqueue 2 in Q2 i.e 1,2

Step 2: perform 1 dequeue and 1 enqueue simultaneously for 1 time in Q2 i.e 2,1 (Head is pointing at 2)

Step 3: enqueue 3 in Q2 i.e 2,1,3

Step 4: perform 1 dequeue and 1 enqueues in simultaneously for 2 times in Q2 i.e 2,1,3 → 1,3,2 → 3,2,1 (head pointing at 3 now)

Step 5:  Enqueue 4 in Q2 i.e 3,2,1,4

Step 6: perform 1 dequeue and 1 enqueues in simultaneously for 3 times in Q2 i.e 3,2,1,4 → 2,1,4,3 → 1,4,3,2 → 4,3,2,1

So the number of enqueue operations in Q1 is 0.

The question was bad in the sense that it didn’t say that the array size of Q2 is greater than 4 so solving conventionally with rear and front keeping the size limitation will not work same with the case if we consider it a circular queue.

2
2
Aren't we using extra variable to reverse the queue.
0
0
edited by

@asr1410 No we don't need to use any extra variable. We can perform $Enqueue$ and $Dequeue$ together as $Enqueue(Q1, Dequeue(Q2))$

1
1

7 Answers

27 votes
27 votes

Answer $\color{red}{\text{0 ENQUEUE}}$ to Q1.

Credit of the answer goes to shishir__roy

From Wiki-

By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue.

Head means Dequeue.

We want the following situation.

Before that, One quick question- Can you reverse a queue $\color{blue}{\text{in place}}$ by just using simple enqueue and dequeue as asked in question?.

If queue is just having 2 elements then yes otherwise no.

Let me first divide 4 elements into 2-2 elements each.

Step 1

 

Till now, NO enqueue to Q1.

Now reverse Q2.  This doesn’t cost any ENQUEUE to Q1

Step2:


Step 3:

 

 

Step 4:

Step 5:

 

Step 6:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

GO Classes - GATE CSE 2023 (Live + Recorded) Course

https://www.goclasses.in/

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

edited by

4 Comments

I think, very few would have answered 0, hope these 2 marks won’t affect the rank much.
1
1
Can we not swap the head and tail pointers and change the increments and decrements in the Enqueue and Dequeue operations? Then we already have a reversed queue( It does follow all the properties the same except the array is now logically inverted).
Now, we can just dequeue from Q1 and Enqueue into Q2.
0
0

aspirant22 No we can’t we are strictly told that the only operations possible are Enqueue and dequeue

0
0
11 votes
11 votes

 

we can extend on the previous idea that – “we can reverse queue if its length is 2” 

we can say (using 2 queue) – “we can reverse given queue by adding element by element in second queue and then adjusting the second queue such that it is in reverse order(after every enqueue on second queue)”

 

for given question, 

  1. we add 1st element from q1 to q2, since its just one element q2 is already in correct reverse order (considering only the elements in q2).
  2. we add 2nd element from q1 to q2, now we have to adjust q2 (contains 1,2) such that these 2 elements rest in correct reverse order. (we’ll perform 1 enqueue and 1 dequeue on q2. now q2 contains (2,1).
  3. we now add 3rd element and again adjust q2 to correct reverse order, so we’ll need 2 enqueue and 2 dequeue operations.
  4. for 4th element we’ll need 3 enqueue and 3 dequeue operations.

so in total we did 0 enqueue on q1

3 Comments

I didn’t get this, if you dequeue Q2, the head pointer will move to the next position, making that cell empty, and when you enqueue 1, it will be in the 3rd position, considering array index starts at 1, but you have put 1 in 2nd position. How?

0
0

You're only complicating your answer and thought process, think of queue as an atomic construct, don't go on how it's implemented, and just fyi any correct implementation of queue will be enough to execute this operation.

2
2
You are amazing 🤩
0
0
3 votes
3 votes
According to me answer should be 3, we can use this approach-

X= dequeue(Q1)
Q2. Enque(X)
Repeat this 3 times now
Q1 is 4....
And q2 is 123.
Now
X=Deque q2
Q2. Enque(x)
Q2-> 231
Repeat again
Q2->312
Now deque this 3 from q2 and enque this in q1 this will be the first operation and similarly we will put 2 and 1 also in that order we will get 4321 in q1 in just 3 enque operations.

3 Comments

The question clearly says without using any additional storage. Then how can this be done in only 3?

0
0
But they have given no additional storage. So you cannot store the enqueue variable
0
0
We'll have to use one variable anyways for simultaneous enque deque. And lets say im not using x variable im doing this instead

Q2. Enque(q1.deque)

Then i wont be using any additional storage
1
1
1 vote
1 vote

We should consider Q2 to be an array of size greater than length 4, then only the answer will come.

Step 0: Enqueue 1 in Q2, it is already sorted,

Step 1: Enqueue 2 in Q2 i.e 1,2

Step 2: perform 1 dequeue and 1 enqueue simultaneously for 1 time in Q2 i.e 2,1 (head pointing at 2 now)

Step 3: enqueue 3 in Q2 i.e 2,1,3

Step 4: perform 1 dequeue and 1 enqueues in simultaneously for 2 times in Q2 i.e 2,1,3 → 1,3,2 → 3,2,1 (head pointing at 3 now)

Step 5:  Enqueue 4 in Q2 i.e 3,2,1,4

Step 6: perform 1 dequeue and 1 enqueues in simultaneously for 3 times in Q2 i.e 3,2,1,4 → 2,1,4,3 → 1,4,3,2 → 4,3,2,1

So the number of enqueue operations in Q1 is 0.

The question was bad in the sense that it didn’t say that the array size of Q2 is greater than 4 so solving conventionally with rear and front keeping the size limitation will not work same with the case if we consider it a circular queue