Implementation of Stack and Queue

Question

In implementation of queue using stack, deletion of second element from front take Ο(n) time, when insertion take Ο(1) time.

Is it a true statement ?

Well it can be true isn't it ?

because suppose elements come we simply push them without taking care of the order in which they are inserted so O(1) time nd for delete pop every one of them and push it into another stack and pop the first element so O(n).

And this statement

 In implementation of queue using stack, deletion of second element from front take Ο(1) time, when insertion take Ο(n) time.

Is also correct.  Here because we are taking care of order in which elements are inserted into the stack which makes time complexity change.

Approach:

enQueue(q, x)
  1) While stack1 is not empty, push everything from satck1 to stack2.
  2) Push x to stack1 .
  3) Push everything back to stack1.

dnQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it

Am i right?

Comments

Since there will be two stacks let s1 and s2.

Enqueue will be done in s1 directly with O(1) time and deque will be done from s2.here if s2 is empty then first transfer all s1 element in s2 then pop from s2 which is O(n) for first element while for second element it is just O(1).

---

Yes. The implementation you are talking about is compromising dequeue, right?

So enqueue should be O(1)

After pop, if you didn't transfer all elements from s1 back, how will you perform enqueue in O(1)?

---

Why would we transfer all element in s1 back if we can perform enqueue operation directly. here only deque operation is compromising and only in case if s2 is empty, we are transferring all elements of s1 in s2.

After transfer If we perform enqueue in s1 now still it is following the queue FIFO property 'the rear element will be top element of s1 and front element will be top element of s2'

and yes the implementation i'm talking about is compromising deque.

In my perspective deletion of second element will take O(1) time only when deletion of first element already have been performed otherwise it will take O(n) time due to first and second element both in consideration together.