retagged by
18,204 views
34 votes
34 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________________.

 

retagged by

6 Answers

51 votes
51 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
30 votes
30 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 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.
1 votes
1 votes

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

Answer:

Related questions

40 votes
40 votes
3 answers
1