GATE CSE 2022 | Question: 52

Question

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________________.

 

Comments

@tusharb @Abhrajyoti00 how we can consider size of Q2 > 4? w/o mentioning in qn?

and if in place of min , if max was asked then ans should be 6 in this case right?

---

@MANSI_SOMANI Max would be infinite
just keep on enque-ing and deque-ing in Q1 only, don’t put them in Q2

---

@JAINchiNMay right got it 

but how can we consider size of Q2>4 (as mentioned by @tusharb above but i think there is no need to take more than 4) w/o any mention in the qn? 

Answer 1

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/

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

Comments

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.

---

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

---

You’re just focusing on how many enqueue operations costs to Q1, (In this question prof has also mentioned without using any additional storage ), but specifically at the last iteration of reversing Q2 i.e. 3-2-1-4 to 4-2-3-1 on Q2, @shishir__roy you have cleverly used function call stack’s memory for storing the currently dequeued element and again enqueing that element to Q2, there by reversing the queue Q2's elemnts one by one. 😂😂 Nice approach.. but still its using additional memory/storage (though at run time) you see right?

Answer 2

 

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 2^nd 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 3^rd element and again adjust q2 to correct reverse order, so we’ll need 2 enqueue and 2 dequeue operations.
4. for 4^th element we’ll need 3 enqueue and 3 dequeue operations.

so in total we did 0 enqueue on q1

Comments

You are amazing 🤩

---

(In this question prof has mentioned without using any additional storage ), but specifically at the last iteration of reversing Q2 i.e. 3-2-1-4 to 4-2-3-1 on Q2 @shishir__roy you cleverly used function call stack’s memory for storing the currently dequeued element and again enqueing that element to Q2, there by reversing the queue Q2's elemnts one by one. 😂😂 Nice approach.. but still its using additional memory/storage (though at run time) you see right?

---

@swaroopsahoo without using additional storage means algorithm's space complexity shouldn't exceed $O(1)$.

Some authors even consider/allow $O(logn)$ space complexity as NOT using additional storage (in-place algorithm).

Answer 3

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.

Comments

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

---

But they have given no additional storage. So you cannot store the enqueue variable

---

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

Answer 4

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