Sunday, February 8, 2015

Implement queue with stack

This is a brilliant question with a brilliant answer: use two stacks!


public class Queue {
 private Stack in;
 private Stack out;
 public Queue () {
  in = new Stack();
  out = new Stack ();
 }
 public void add(E ele) {
  in.push(ele);
 }
 public E poll() {
  if (out.isEmpty()) {
   while (!in.isEmpty())
    out.push(in.pop());
  }
  if (out.isEmpty())
   throw new NullPointerException("No element left!");
  return out.pop();
 }

 public static void main(String[] args) {
  Queue q = new Queue();
  q.add(1);
  q.add(2);
  q.add(3);
  System.out.println(q.poll());
  q.add(4);
  System.out.println(q.poll());
  System.out.println(q.poll());
  q.add(5);
  System.out.println(q.poll());
  q.add(6);
  System.out.println(q.poll());
  System.out.println(q.poll());
  //System.out.println(q.poll());
 }

}

No comments:

Post a Comment