Method addFirst

02Lab-Queues/Deque.java:45–55

(Item item)

    // add the item to the front
    public void addFirst(Item item) {
        validate(item);
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.prev = null;
        first.next = oldFirst;
        if (isEmpty()) last = first;
        else oldFirst.prev = first;
        n++;
    }

    // add the item to the back
    public void addLast(Item item) {