JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP4 Queue Implementation Using Stack

In this Probole we Learned who to Implement Queue using the Stack

Using 2 Stack

Now here just we follow all the Steps that we followed in the Previous Lecture We 2 Stack Required Stack1 and Stack2

push(x)

Put all the Element Stack1 to Stack2

put x into the Stack1

put all the elementof Stack 2 into the Stack1

pop()

Remove the Top Element by Stack1 this is the Process Follow again and again

Notes

Note: Zoom for Better Understanding

Code Zone!

Time Complexity:O(N) Linear Time for the Iteration. O(N) Time Tale for the Push() Operation
Space Complexity:O(N) O(N) for the Recursive Stack Space.

But Interviewer Not happy this Solution Becouse we used 2 Stack and O(N) time for the Push() Operation, Now Time To Optimized the Approch

Thoughtg Process

We Required the 2 Stack again Input and Output

Put the x into the Stack1

at pop() time we moved all the emenet into the Stack2 and top of the Stack2 is the our Top Element

Code Zone!

Time Complexity:O(1) Becouse: pop() -> pop can be O(1) or O(n) . O(1) when all elements are already shifted . So we just need to delete the element . So here we can say that time complexity can be O(1) or amortised O(1)
Top() -> Top can be O(1) or O(n) . O(1) when all elements are already shifted . So we just need to return the element. So here we can say that time complexity can be O(1) or amortised O(1)
Space Complexity:O(2N) Becouse we Used a 2 Stack.