Recently I encountered a trivial but interesting question. "How to implement a queue using two stacks ? ". My first reaction was "Why would I do that ..? " But if I am forced to do such a thing, how would I go about doing it ? So, here is how we implement a queue using two stacks.
Logic : We'll implement a FIFO queue using two stacks. Lets call the stacks Instack and Outstack. An element is inserted in the queue by pushing it into the Instack. An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
We start with a Stack Interface :
public interface Stack {
void push( Object x );
Object pop( );
Object top( );
boolean isEmpty( );
void makeEmpty( );
}and a class that implements this interface :
public class ArrayStack implements Stack {
private Object [ ] theArray;
private int topOfStack;
private static final int DEFAULT_CAPACITY = 10;
public ArrayStack( ) {
theArray = new Object[ DEFAULT_CAPACITY ];
topOfStack = -1;
}
public boolean isEmpty() {
return topOfStack==-1;
}
public void makeEmpty() {
topOfStack= -1;
}
public Object pop() {
if(!isEmpty())
return theArray[topOfStack--];
else
return null;
}
public void push(Object x) {
if(!isFull())
theArray[++topOfStack] = x;
}
public Object top() {
return theArray[topOfStack];
}
public static void main(String[] args) {
//Not relevant to our code
}
public boolean isFull()
{
return (topOfStack == theArray.length);
}
}Now we come to actual class that implements a Queue using two stacks.
public class stackQueue {
ArrayStack inStack = new ArrayStack();
ArrayStack outStack = new ArrayStack();
public static void main(String[] args)
{
stackQueue queue = new stackQueue();
queue.enqueue(new String("first"));
queue.enqueue(new String("second"));
queue.enqueue(new String("third"));
queue.enqueue(new String("fourth"));
queue.enqueue(new String("fifth"));
System.out.println("1. " + queue.dequeue());
System.out.println("2. " + queue.dequeue());
System.out.println("3. " + queue.dequeue());
System.out.println("4. " + queue.dequeue());
System.out.println("5. " + queue.dequeue());
}
public void enqueue(Object value)
{
inStack.push(value);
}
public Object dequeue()
{
if(outStack.isEmpty())
{
while( ! inStack.isEmpty())
{
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
}
