CODEWITHSUNDEEP
data-structuresstackqueue
Drool
Drool

Reputation: 129

Why are we having elements push back to stack 1 from stack 2

Recently I have come across an algorithm on how to build a queue using 2 stacks which is as follows:

Method 1 (By making enQueue operation costly): This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)
  1) While stack1 is not empty, push everything from stack1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.
Here time complexity will be O(n)


deQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it
Here time complexity will be O(1)

Now this algorithm makes sense, except the third point on why we are pushing everything back on stack 1. Why cant we use stack 2 as a queue (during enqueue operation)

Upvotes: 0

Views: 222

Answers (1)

Rax
Rax

Reputation: 375

Why is everything being pushed back on stack1

This is being driven by the fact that when you perform dequeue operation you pop an element from stack 1.

Suppose you have three push operation x1, x2, x3 in the same order. Since your dequeue operation is always happening from stack1, you have to ensure that x1 is at the top, with x2 at number two and x3 at number three from top. This can only be ensured by the third point.

In the algorithm, you have mentioned above enqueue and dequeue both are being performed on stack1.

Why cant we use stack 2 as a queue (during enqueue operation)

In this case, you will have to perform dequeue operation on stack 1.

enqueue(q,x):

  1. push on to stack 2. O(1)

deQueue(q):

  1. If stack1 is not empty then pop from stack1.

  2. If stack1 is empty

    2.1 If stack2 is also empty, throw an error.

    2.2 Transfer all from stack2 to stack1. Now pop the top from stack1. Amortized complexity of dequeue will be O(1) because the number of transferred element equals the number of popped element from stack1.

Upvotes: 2

Related Questions