// Path: src/main/java/io/github/marioluan/datastructures/priority/queue/LinkedListIterator.java
// public class LinkedListIterator<T extends Comparable<T>>
//         implements Iterator<T> {
//     private Node<T> cursor;
// 
//     /**
//      * Constructs the iterator by pointing its cursor to the head.
//      */
//     public LinkedListIterator(Node<T> head) {
//         this.cursor = head;
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     public boolean hasNext() {
//         return this.cursor != null;
//     }
// 
//     /**
//      * Operation not permitted.
//      * 
//      * @throws UnsupportedOperationException
//      */
//     public void remove() {
//         throw new UnsupportedOperationException();
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     public T next() {
//         if (!hasNext())
//             throw new NoSuchElementException();
// 
//         T oldItem = this.cursor.data;
//         this.cursor = this.cursor.next;
// 
//         return oldItem;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/Node.java
// public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
// 
//     /**
//      * The value of the node.
//      */
//     public T data;
// 
//     /**
//      * A link to the next node.
//      */
//     public Node<T> next;
// 
//     /**
//      * A link to the previous node.
//      */
//     public Node<T> prev;
// 
//     /**
//      * Construct a new node with the given data.
//      * 
//      * @param data
//      */
//     public Node(T data) {
//         this.data = data;
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     @Override
//     public int compareTo(Node<T> that) {
//         return this.data.compareTo(that.data);
//     }
// 
//     /**
//      * Checks whether there is a link to next node.
//      * 
//      * @return whether the next field is not null
//      */
//     public boolean hasNext() {
//         return this.next != null;
//     }
// 
//     /**
//      * Checks whether there is a link to previous node.
//      * 
//      * @return whether the prev field is not null
//      */
//     public boolean hasPrev() {
//         return this.prev != null;
//     }
// 
// }


import java.util.Iterator;
import java.util.NoSuchElementException;
import io.github.marioluan.datastructures.priority.queue.LinkedListIterator;
import io.github.marioluan.datastructures.Node;
     * <strong>Time complexity:</strong> O(1)<br>
     * 
     * @return returns the last data
     */
    public T removeLast() {
        if (this.isEmpty())
            throw new NoSuchElementException();

        Node<T> oldTail = this.tail;
        this.tail = this.tail.prev;

        if (this.tail != null)
            this.tail.next = null;

        this.size--;

        // when the dequeue becomes empty, head == tail
        if (this.isEmpty())
            this.head = null;

        return oldTail.data;
    }

    /**
     * Return the iterator over items in order from front to end.
     * 
     * @return returns a new instance
     */
    @Override
    public Iterator<T> iterator() {
// Path: src/main/java/io/github/marioluan/datastructures/priority/queue/LinkedListIterator.java
// public class LinkedListIterator<T extends Comparable<T>>
//         implements Iterator<T> {
//     private Node<T> cursor;
// 
//     /**
//      * Constructs the iterator by pointing its cursor to the head.
//      */
//     public LinkedListIterator(Node<T> head) {
//         this.cursor = head;
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     public boolean hasNext() {
//         return this.cursor != null;
//     }
// 
//     /**
//      * Operation not permitted.
//      * 
//      * @throws UnsupportedOperationException
//      */
//     public void remove() {
//         throw new UnsupportedOperationException();
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     public T next() {
//         if (!hasNext())
//             throw new NoSuchElementException();
// 
//         T oldItem = this.cursor.data;
//         this.cursor = this.cursor.next;
// 
//         return oldItem;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/Node.java
// public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
// 
//     /**
//      * The value of the node.
//      */
//     public T data;
// 
//     /**
//      * A link to the next node.
//      */
//     public Node<T> next;
// 
//     /**
//      * A link to the previous node.
//      */
//     public Node<T> prev;
// 
//     /**
//      * Construct a new node with the given data.
//      * 
//      * @param data
//      */
//     public Node(T data) {
//         this.data = data;
//     }
// 
//     /**
//      * {@inheritDoc}
//      */
//     @Override
//     public int compareTo(Node<T> that) {
//         return this.data.compareTo(that.data);
//     }
// 
//     /**
//      * Checks whether there is a link to next node.
//      * 
//      * @return whether the next field is not null
//      */
//     public boolean hasNext() {
//         return this.next != null;
//     }
// 
//     /**
//      * Checks whether there is a link to previous node.
//      * 
//      * @return whether the prev field is not null
//      */
//     public boolean hasPrev() {
//         return this.prev != null;
//     }
// 
// }


// Path: src/main/java/io/github/marioluan/datastructures/queue/Deque.java
import java.util.Iterator;
import java.util.NoSuchElementException;
import io.github.marioluan.datastructures.priority.queue.LinkedListIterator;
import io.github.marioluan.datastructures.Node;

     * <strong>Time complexity:</strong> O(1)<br>
     * 
     * @return returns the last data
     */
    public T removeLast() {
        if (this.isEmpty())
            throw new NoSuchElementException();

        Node<T> oldTail = this.tail;
        this.tail = this.tail.prev;

        if (this.tail != null)
            this.tail.next = null;

        this.size--;

        // when the dequeue becomes empty, head == tail
        if (this.isEmpty())
            this.head = null;

        return oldTail.data;
    }

    /**
     * Return the iterator over items in order from front to end.
     * 
     * @return returns a new instance
     */
    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator<T>(this.head);