/*******************************************************************
* 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:
* View the first existing element added to the queue.
*
* Time Complexity of Solution:
* Best = const; Worst = O(n).
*
* Technical Details:
* 0] If the output stack is not empty, peek into it and return
* the element.
* 1] Otherwise, empty the input stack into the output stack.
* 2] Now peek into the output stack and return the element.
*
****************************************************************/
public E peek() {
if (!output.isEmpty()) {
return output.peek();
}
while (!input.isEmpty()) {
output.push(input.pop());
}
return output.peek();
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class QueueWithStackTest {
/**
* Test of peek method, of class QueueWithStack.
*/
@Test
public void testPeek() {
System.out.println("peek");
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());
assertEquals(data[0], queue.peek());
assertEquals(data[0], queue.peek());
}
}