Blog # 30 : Stack and Queues

For beginners :

Implement Stack and Queue by yourself. Many of you have not done it yet. Implement all the primitive operations on Stack and Queue. Try to implement it without using an Array.

For others:

1. Implement a Stack using 2 Queues.
2. Implement a Queue using 2 Stacks. [Implementing any structure means all the primitive operations have to be performed].

Code it.


P.S. - Its not bad to be a beginner :)



Solution :


Basically in this problem, You need not to be efficient in terms of time and space complexity. You just need to think how this goal will be achieved. 
For Stack using 2 Queues basic idea is, 
For PUSH operation:
ENQUEUE all the elements in only one of the Queue [after first PUSH, insert into non-empty Queue] (using flag is an option or you may check this as a condition of emptiness).
For POP operation:
DEQUEUE all the elements except one from the non-empty Queue and ENQUEUE all of these De-queued elements of first Queue into the second one making first Queue empty.

Similarly for Queue using 2 Stacks.