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();
}
}
13 comments:
I think the code is borken. Shouldn't you be updating the instack in case of dequeue. Run your code on enqueue 3, 2, 1; dequeue ; enqueue 4; dequeue; dequeue; dequeue.
supervb explanation..
Thanks...glad to help
Thanks for posting this. I heard there was an implementation of a queue with two stacks that had constant amortized cost for both enqueue and dequeue operations. Every way I was able to come up with not satisfy this requirement. This solution does however! Thanks again for posting this.
Excellent
nice work!!
Why not just return instack.pop() when trying to dequeue in the case of outstack.isEmpty() == true?
public int dequeue()
{
int result = -1 ;
if(! Instack.isempty())
{
while( ! Instack.isempty())
{
Outstack.push(Instack.pop());
}
result = Outstack.pop();
while (! Outstack.isempty())
{
Instack.push(Outstack.pop());
}
}
return result; // -1 means there is no element in the stacks
}
There are two options.
1. Make dequeue operation expensive, enqueue fast (your approach).
2. Make enqueue operation expensive, dequeue fast. In this case, we can populate outStack while enqueing inStack, so that while performing dequeue, only thing to be done is pop().
YOUR BACKGROUND SUCKS.
You need to pop all the element in the outstack into instack after dequeue
Thank you for helping me with my homework :)
what is the size of the queue, if the stacks of N-size are used?
I think it varies from N~2N. right??
Post a Comment