recategorized by
7,335 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.
recategorized by

3 Answers

Best answer
59 votes
59 votes

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

33 votes
33 votes
6 answers
1
Kathleen asked Oct 4, 2014
33,092 views
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that...
29 votes
29 votes
6 answers
2
Kathleen asked Oct 5, 2014
4,888 views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...