/* 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
    {
        private Item item;
        private Node next;
        private Node prev;
    }

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

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

    // 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;
        if (head == null)
            tail = node;
        else
            head.prev = node;
        head = node;
        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 = node;
        else
            tail.next = node;
        tail = node;
        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 (head == tail)           // head.next == null
        {
            head = null;
            tail = null;
        }
        else
        {
            Node prevHead = head;
            head = head.next;
            head.prev = null;
            prevHead.next = 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)           // tail.prev == null
        {
            head = null;
            tail = null;
        }
        else
        {
            Node prevTail = tail;
            tail = tail.prev;
            tail.next = null;
            prevTail.prev = 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;
        }
    }
}