/* vim: set expandtab tabstop=4 shiftwidth=4 : */

import java.util.Iterator;

public class Deque<Item> implements Iterable<Item>
{
    private Node head;
    private Node tail;
    private int n;

    private class Node
    {
        Item item;
        Node next;
        Node prev;
    }

    // construct an empty deque
    public Deque()
    {
        head = null;
        tail = null;
        n = 0;
    }

    // is the deque empty?
    public boolean isEmpty()
    {
        return (head == null);
    }

    // return the number of items on the deque
    public int size()
    {
        return n;
    }

    // insert the item at the front
    public void addFirst(Item item)
    {
        if (item == null) throw new java.lang.NullPointerException();
        Node node = new Node();
        node.item = item;
        node.next = head;
        node.prev = null;
        head = node;
        if (tail == null) tail = head;
        n++;
    }

    // insert the item at the end
    public void addLast(Item item)
    {
        if (item == null) throw new java.lang.NullPointerException();
        Node node = new Node();
        node.item = item;
        node.next = null;
        node.prev = tail;
        if (tail == null)
        {
            head = tail = node;
        }
        else
        {
            tail.next = node;
            tail = tail.next;
        }
        n++;
    }

    // delete and return the item at the front
    public Item removeFirst()
    {
        if (head == null) throw new java.util.NoSuchElementException();
        Item item = head.item;
        if (tail == head) tail = tail.next;
        head = head.next;
        head.prev = null;
        n--;
        return item;
    }

    // delete and return the item at the end
    public Item removeLast()
    {
        if (tail == null) throw new java.util.NoSuchElementException();
        Item item = tail.item;
        if (head == tail)
        {
            head = tail = null;
        }
        else
        {
            tail = tail.prev;
            tail.next = null;
        }
        n--;
        return item;
    }

    // return an iterator over items in order from front to end
    public Iterator<Item> iterator() { return new DequeIterator(); }

    private class DequeIterator implements Iterator<Item>
    {
        private Node current = head;

        public boolean hasNext() { return current != null; }
        public void remove() { throw new java.lang.UnsupportedOperationException(); }
        public Item next()
        {
            if (current == null) throw new java.util.NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}