mock test

Question

Consider the following statements:
S₁ : Implementation of stack using queue, deletion of second element from top of stack time complexity Ο(n), when insertion take Ο(1) time.
S₂ : In implementation of queue using stack, deletion of second element from front take Ο(1) time, when insertion take Ο(n) time.
Which of the following is correct ?

plz explain how second statement is true

Comments

both statements are correct, it depends on implementation you can make either insertion or deletion costly to O(n) and another operation can be in O(1)

---

u mean reverse of  statement s1 and s2 both also true

but how deletion always take O(n) time

---

both statements are independent.

Answer 1

Both correct.

In Stack using queue we can simply enqueue it O(1) , But while popping we can't directly dequeue it, we must dequeue untill second last element into aux queue and then dequeue (pop)the last element to maintain LIFO order. O(n)

In Queue using stack insertion needs O(n) because push in first stack and pop again push in second stack. Deletion is simply pop top of second stack O(1)

Ref: https://gateoverflow.in/189468/made-easy-test-series