/**
 * Write a description of class Deque here.
 *
 * @author (your name)
 * @version (a version number or a date)
 */

import java.util.NoSuchElementException;

public class Deque<E> implements Queue<E>
{
    private static class LLNode<E>
    {
        private E data;
        private LLNode<E> next;
        private LLNode<E> previous;

        public LLNode(E data, LLNode<E> next, LLNode<E> previous)
        {
            this.data = data;
            this.next = next;
            this.previous = previous;
        }
    }


    private LLNode<E> head, tail;
    private int size;

    public boolean isEmpty()
    {
        return head == null;
    }


    public void enqueueFront(E newData)
    {
        if (isEmpty()) {
            head = tail = new LLNode<E>(newData, null, null);


        } else {
            tail.next = new LLNode<E>(newData, null, null);
            tail = tail.next;
        }

        size++;
    }

    public void enqueueBack(E newData)
    {
        if (isEmpty()) {
            head = tail = new LLNode<E>(newData, null, null);
        } else {
            tail.previous = new LLNode<E>(newData, null, null);
            tail = rail.previous;
        }

        size++;
    }

    public E dequeueFront()
    {
        if (!isEmpty()) {
            E temp = head.data;
            head = head.next;
            size--;

            if (size == 0)
                tail = null;

            return temp;
        } else {
            throw new NoSuchElementException();
        }
    }

    public E dequeueBack()
    {
        if (!isEmpty()) {
            E temp = head.data;
            head = head.previous;
            size--;

            if (size == 0)
                tail = null;

            return temp;
        } else {
            throw new NoSuchElementException();
        }
    }

    public E peekFront()
    {
        if (!isEmpty())
            return head.data;
        else
            throw new NoSuchElementException();
    }

    public E peekBack()
    {
        if (!isEmpty())
            return tail.data;
        else
            throw new NoSuchElementException();
    }

    public String toString()
    {
        String s = "LLQueue (size = " + size + "), containing (front to back): ";
        LLNode<E> temp = head;
        while (temp != null) {
            s += temp.data + " ";
            temp = temp.next;
        }
        return s;
    }
}