26 Jan 2014

Queue with two Stacks

Problem Statement: 
         Implement Queue using two stacks.

Fig: Queue using two stacks

Source Code Link

I expect you are aware of operations that ADTs(Abstract Data Types) Queue and Stack supports. All we have to do is implement Enqueue and Dequeue opertions using operations of a Stack, i.e. push, pop , peek , isEmpty and size.

     1st Approach(inefficient):
             Suppose we have two stacks say S1 and S2 , we use S1 to push elements , when en-queue operation of queue is called, and when de-queue is called we pop everything out of S1 and push to S2, and pop the  top element from S2, and again push everything to S1 by popping out from S2.

Enqueue Operation:
    push to S1

Dequeue Operation:
   1. Pop everything from S1 and push to S2.
   2. Pop top element of S2 when S1 gets empty.
   3. Push everything back to S1 from S2.

Here clearly our Dequeue operation is costly , and there lies one more approach by which we can improve on this.

2nd Approach: (Efficient)
    This approach is slight modification to the above logic in order to achieve efficiency in the "dequeue"operation.
In the above approach we are unnecessarily pushing elements from S2 to S1 , i.e. Step 3 of Dequeue operation as shown above. The trick is to pick the top element of S2 if its not empty , if it is then push everything from S1 to S2 and return top element of S2.

Summary :
Enqueue Operation:
  1.  push to S1

Dequeue Operation:
    1. If S2 is not Empty
              - pop top element of S2
    2. If S2 is empty
              - push everything from S1 to S2 and pop top element of S2.

The link to the code is given above please refer to it.

Please post your comments and suggestions.
Happy Coding !!:)

No comments:

Post a Comment