GATE CSE 1994 | Question: 26

Question

A queue $Q$ containing $n$ items and an empty stack $S$ are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the TOP of the stack, and the order of all other items are preserved. Show how this can be done in $O(n)$ time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

Comments

Transfer the items in three sequential passes:

1. Transfer all elements from Q to S.

2. Transfer all elements from S back to Q.

3. Transfer all elements from Q to S again.

Answer 1

We can do this be first extracting items one by one from $Q$, and inserting them to $S$. After all items are done, $S$ will contain the items in reverse order. Now, pop the elements from $S$ and insert to $Q$. After this operation, items in $Q$ will be in reverse order from the starting. Now, extract items from $Q$ and push on to stack and we are done. 

Do
Delete an item from Q
Push the item to S
While (! empty Q); 
Do
Pop an item from S
Insert the item to Q
While (! empty S); 
Do
Delete an item from Q
Push the item to S
While (! empty Q); 

Comments

anyone pls explain in what cases we use 2 stacks?

---

No, this can be done by using one stack and one queue, which is given in question.

---

it's like a loop only that we are doing it 2 times.

Answer 2

The given requirement can be achieved by,

1.Transfer the n elements from queue  Q to  stack S. Now, elements present in stack is in reverse order. These step require n iterations.

2. Transfer the n elements present in stack to queue one by one using pop(S) operation.These step require n iterations.

3. Perform Step 1.

So total iteration = n+n+n = 3n = O(n).

Comments

perfect

Answer 3

"the item at the front of queue is on the TOP of the stack, and the order of all other items are preserved"

To do this we need an additional stack of size 2 apart from input Queue (Q) and Stack (S). Let's say our new stack (of size 2) is S₂.
1. First, we have to take the 1st element of the queue and put it on to the stack S₂ and keep there.
2. We have to do step 3 and 4 in a loop until Queue (Q) will be empty.
3. We have to take the next element from the queue (Q) and put it on to the stack S₂ and pop immediately.
4. Store that element in the stack S.
5. In the end, we have to pop the first element from the stack S₂ and put on to the Stack S.


To do this time taken will be O(n) and only a constant amount of space is required.

Hope this answer helps...!!!🙂


 

Comments

@ Gupta731
No, I didn't reverse all the elements. You did not understand my answer correctly. I have put all the elements as it is except the 1st element. Only the 1st element of the queue is on the top of the stack and the remaining elements are as it is onto the stack.

---

This is exactly what the question is asking for!!

---

Can’t say your answer to be wrong. But it’s not clear by the question what does : 

and the order of all other items are preserved

mean. Another ambiguous q.

Answer 4

"the order of all other items are preserved"   means

 When A is at the top it's next should be 'B' and then 'C'   i.e   Order in which queue items are present, They should be present in the same order in stack. 

Example: ABCDEF is present in the queue from front to rear ( A is front and F is at rear)

Step 1 : Delete A from Queue and push it to stack and pop it from stack and add the popped element to the end of the queue.
As a result,  You'll get BCDEFA

Step 2 : push all these elements to stack 
Now stack contains BCDEFA (from bottom to top)

Step 3 : pop out all elements one by one from the stack and  in the meanwhile insert them in the queue

Now your queue contain AFEDCB

Step 4 : Now again Delete A from Queue and push it to stack and pop it from stack and add the popped element to the end of the queue.

Now your queue contains FEDCBA

Step 5 :  Now deque all elements one by one and push them into the stack in the same order as they are dequeued

Finally Your Stack consists of ABCDEF from Top to Bottom 
This can be done in O(n) time and we are not using any additional storage other than what they've given in the question.

Answer 5

Hence it is solved. If there is any mistake please let me know.