// file:    Deque.java
// author:  Robert Keller
// purpose: Implement the Deque interface using bi-directional linked lists.

/**
 * A Deque (double-ended queue) is a repository for objects that maintains
 * insertion order.  Objects can be inserted and removed from either in.
 */

interface Deque
{
/**
 * Insert an Object at the front of the Deque.
 *
 * @param item the Object to be inserted
 */

void enqueueFront(Object item);


/**
 * Remove an Object from the back of the Deque.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the Queue is empty
 */

Object dequeueBack() throws EmptyQueueException;


/**
 * Insert an Object at the back of the Deque.
 *
 * @param item the Object to be inserted
 */

void enqueueBack(Object item);


/**
 * Remove an Object from the front of the Deque.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the Queue is empty
 */

Object dequeueFront() throws EmptyQueueException;


/**
 * Indicate whether or not the Deque is empty
 *
 * @return boolean indicating whether or not the Deque is empty
 */

boolean isEmpty();

}