Thursday 10 September 2015

Implement a queue using two stacks

Implement a queue using two stacks
Keep 2 stacks, let's call them inbox and outbox.

Queue:
- Push the new element onto inbox.

Dequeue:
- If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
- Pop and return the top element from outbox.

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.

package api.implement;
import java.util.Stack;
public class Queue<E> {

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }
}

package api.implement;
public class TestQueue {
       public static void main(String[] args) {
             
              Queue<String> queue = new Queue<String>();
              queue.queue("rajesh");
              queue.queue("sattu");
              queue.queue("sattu1");
             
              System.out.println(queue.dequeue());
              System.out.println(queue.dequeue());
       }
}
Output:
rajesh
sattu

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...