QUEUE USING STACKS

Question

Q.What will be time complexity of enqueue and dequeue operation when a queue is implemented using two stacks.

Comments

any one of the two operations(enqueue or dequeue) can be done in O(1) time and the other one in O(n) time..

in simple words,

if enqueue-> O(1) then dequeue-> O(n)

if enqueue-> O(n) then dequeue-> O(1)

---

@ joshi_nitish

enqueue

{

push()/*it will take 0(1) time since we are doing for n elements so overall 0(n) */

}

is it correct but didn't get how it will take 0(1) only as you are suggesting and please explain how it will take 0(1) for dequeue.

---

@junaid

qsn has asked for enque and deque, this simply means enque or deque of just one element(recall from a fact that if i say what is time complexity of insertion or deletion in heap??...you will say O(logn), this is so because you are answering for one element only).

now for deque part,

since you are inserting at top of stack this means, you have to delete element from bottom(because in queue insertion and deletion are done at opposite ends).....for this you have to shift n-1 top element to 2nd stack delete bottom most element and then shift back n-1 elements back to 1st stack, it will take,

n-1(popping elements) + n-1(pushing in second stack) + 1(deleting bottom most element) + n-1(shifting back to 1st stack) = 3n-2 = O(n) time..

---

@ joshi_nitish 

I watched this videos.

and your method is different.

please give me your source of this concept.

Answer 1

The time complexity of enqueue and dequeue operation when using 2 stacks

If here enqueue using 2 stacks, then dequeue will use 1 stack is enough

Say, for enqueue we use reverse, push , reverse operations

• So, in reversing all element will push in another stack take O(n) time
• New element will be push ,take O(1) time
• Then push back to the 1st stack will take O(n) time

Now in case of dequeue

• just do pop the element from the front of stack(It will just take O(1) time)

_____________________________________________________________________

We can also do in reverse way, that take enqueue operation in O(1) time and dequeue O(n) time

Comments

@srestha

for Enqueue i Push all element in stack1 if I need Dequeue then I Pop an element from stack1 and Push into stack2 and finally pop from satck2.(If stack2 is empty)

otherwise, I push in stack1 and Pop from stack2

This is right??

---

plz try to understand,question of GATE not such easy

Try to understand the concept first

First of all question for u why do u using 2 stacks?

Why not 1 stack is not sufficient?

Because in queue we need 1 end for pushing and another end for popping

Similar question https://gateoverflow.in/2007/gate2014-2-41

try to understand it

---

Thank you so much