Dequeue
by Isai Damier, Android Engineer @ Google

/*******************************************************************
 * Author: Isai Damier
 * Title: QueueWithStack
 * Project: geekviewpoint
 * Package: datastructure
 *
 * Description: To implement a Queue using Stack datastructure,
 *    two stacks are sufficient: a stack for enqueuing and a stack
 *    for dequeuing. Recall that stacks are LIFO objects (i.e. Last
 *    In First Out), whereas queues are normally FIFO objects (i.e.
 *    First In First Out). Hence although adding elements to a stack
 *    is similar to adding elements to a queue, the removal process
 *    for each datastructure is different.
 *
 *    Notice how in the following implementation queue.enqueue() is
 *    the same as stack.push(). However, two stacks are used for
 *    proper dequeuing.
 ******************************************************************/ 
 import java.util.Stack;

public class QueueWithStack<E> {

  private final Stack<E> input = new Stack<E>();
  private final Stack<E> output = new Stack<E>();

  /***************************************************************
   * Statement:
   *   Remove an element from the queue.
   *
   * Time Complexity of Solution:
   *   Best = const; Worst = O(n).
   *
   * Technical Details:
   *   0] If the output stack is not empty, pop it and return the
   *      top element
   *   1] Otherwise, empty the input stack into the output stack
   *   2] Now pop the output stack and return the element.
   *
   ****************************************************************/
  public E dequeue() {
    if (!output.isEmpty()) {
      return output.pop();
    }
    while (!input.isEmpty()) {
      output.push(input.pop());
    }
    return output.pop();
  }
}

import org.junit.Test;
import static org.junit.Assert.*;

public class QueueWithStackTest {

  /**
   * Test of dequeue method, of class QueueWithStack.
   */
  @Test
  public void testDequeue() {
    System.out.println("dequeue");
    QueueWithStack<Integer> queue = new QueueWithStack<Integer>();
    Integer[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    assertTrue(queue.isEmpty());
    assertEquals(0, queue.size());
    for (int d : data) {
      queue.enqueue(d);
    }
    assertFalse(queue.isEmpty());
    assertEquals(data.length, queue.size());

    for (int i = 0; i < data.length; i++) {
      assertEquals(data.length - i, queue.size());
      assertEquals(data[i], queue.dequeue());
    }

    assertTrue(queue.isEmpty());
    assertEquals(0, queue.size());
  }
}