24 November 2011

Queue using Stack in Java

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.

And a test class for this with output


No comments: