Redirected
3,279 views
4 votes
4 votes

Consider the following statements:

S1 : Implementation of stack using queue, deletion of second element from top of stack time complexity Ο(n), when insertion take Ο(1) time.
S2 : 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 ?

1 Answer

0 votes
0 votes

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

Related questions

2 votes
2 votes
2 answers
1
1 votes
1 votes
1 answer
3