package hw5;

import java.util.NoSuchElementException;

/**

* This is a skeleton file for your homework. Complete the functions below. You

* may also edit the function "main" to test your code.

*

* You should not use any loops or recursions. Your code needs to run in

* constant time. It is OK if your testing code has loops (like in

* checkInvariants).

*

* You must not add fields or static variables. As always, you must not change

* the declaration of any method nor the name of the class or of this file.

*/

public class Deque {

private Node first; // A reference to the first item in the Dequeue (or

// null if empty)

private Node last; // A reference to the last item in the Dequeue (or

// null if empty)

private int N; // The number of items currently in the Dequeue

private class Node {

public T item; // The data stored at this node.

public Node next; // The node to the right (or null if there is no

// node to the right)

public Node prev; // The node to the lett (or null if there is no

// node to the left)

}

/**

* Construct an empty Deque.

*/

public Deque() {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Tests if the Dequeue is empty.

*

* @return true if this Deque is empty and false

* otherwise.

*/

public boolean isEmpty() {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Returns the number of items currenlty in this Deque.

*

* @return the number of items currenlty in this Deque

*/

public int size() {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Inserts an item into the front of this Deque.

*

* @param item the item to be inserted

*/

public void pushFront(T item) {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Inserts an item into the back of this Deque.

*

* @param item the item to be inserted

*/

public void pushBack(T item) {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Removes and returns the item at the front of this Deque.

*

* @return the item at the front of this Deque.

* @throws NoSuchElementException if this Deque is empty.

*/

public T popFront() {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

/**

* Removes and returns the item at the back of this Deque.

*

* @return the item at the back this Deque.

* @throws NoSuchElementException if this Deque is empty.

*/

public T popBack() {

// TODO - Repalce the line below with a correct solution.

throw new RuntimeException("Not implemented");

}

}