in DS recategorized by
7,280 views
32 votes
32 votes
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.
in DS recategorized by
7.3k views

3 Answers

59 votes
59 votes
Best answer

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); 
edited by
by

4 Comments

isn't correct? consider this is the queue given:

1(front) 2 3 4 5(rear)

Now I think the question asks us to order the elements in this way inside the stack:

2(bottom) 3 4 5 1(top) : "the item at the front of queue is on the TOP of the stack, and the order of all other items are preserved"

But this is what the stack will look like using this answer:

5(bottom) 4 3 2 1(top)

@

1
1

@
@
You both can check my answer. Hope it will help.

0
0
If I do a slight modification and delete the elements one by one from the front of the queue and add to the rear just until we get the last element at front and push that in stack. We can repeat this until the queue is empty. Will this method work, will the queue able to distinguish between first and last elements? And what will be the time complexity?
0
0
5 votes
5 votes

"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...!!!🙂


 

edited by

4 Comments


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.

0
0
This is exactly what the question is asking for!!
0
0

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.

0
0
3 votes
3 votes
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).

Related questions