Implementation for a Monotonic Increasing Queue

Question

I am trying to implement a fast Monotonic strictly Increasing Queue using the Java Deque Interface and the LinkedList class. Assume I have an array of int {10, 7, 1, 2, 4, 3, 8}, after performing a monotonic queue on this, am I supposed to have {1, 2, 3, 8} or just {3, 8}?

Based on my implementation, I have {1, 2, 3, 8}.

Attached is my code:

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * A Strictly Monotonic increasing Queue. [1, 2, 3, 6, 8, 12, 16, 23]. Where the largest element is
 * at the back of the Queue (tail of the linkedList).
 * Adapter Design Pattern.
 */
public class MonotonicQueue<E extends Object & Comparable<E>> implements Iterable<E> {

    private final Deque<E> queue;
    private int t = 0;                          // Number of elements in the Queue

    public MonotonicQueue() {
        this.queue = new LinkedList<>();
    }

    private void nullChecker(E obj) {
        if (obj == null)
            throw new NullPointerException();
    }

    public int size() {
        return t;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public void push(E obj) {
        nullChecker(obj);
        if (isEmpty())
            queue.offerFirst(obj);
        else {
            while(!queue.isEmpty() && queue.peekLast().compareTo(obj) >= 0) {
                queue.pollLast();
                t--;
            }
            queue.offerLast(obj);
        }
        t++;
    }

    public E pop() throws EmptyQueueException {
        if (isEmpty())
            throw new EmptyQueueException();
        t--;
        return queue.pop();            // This will return the maximum element (The front element) in the Queue
    }

    public boolean contains(E obj) {
        if (obj == null)
            return false;
        if (isEmpty())
            return false;

        // If obj > the element at the front of the Queue, then the Queue cannot contain obj.
        else if (obj.compareTo(queue.peekLast()) > 0)
            return false;
        else {
            for (E data : this) {
                if (data.compareTo(obj) == 0)
                    return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        Iterator<E> iter = this.iterator();
        while (iter.hasNext()) {
            stringBuilder.append(iter.next());
            if (iter.hasNext())
                stringBuilder.append("--> ");
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return queue.iterator();
    }
}

Thanks in advance.

Answer 1

Monotonic Queue

A monotonic queue can be either increasing or decreasing.

In a Monotonic Increasing Queue, when a new element e is pushed, every queue's element q[i] that violates the condition q[i] >= e, starting from the lowest element, is popped out of the queue.

Likewise

In a Monotonic Decreasing Queue, when a new element e is pushed, every queue's element q[i] that violates the condition q[i] <= e, starting from the lowest element, is popped out of the queue.

Example Monotonic Increasing Queue

5 => [5]
3 => [3] 3 pops out 5
1 => [1] 1 pops out 3
2 => [1, 2]
4 => [1, 2, 4]

Example Monotonic Decreasing Queue

5 => [5]
3 => [5, 3]
1 => [5, 3, 1]
2 => [5, 3, 2] 2 pops out 1
4 => [5, 4] 4 pops out 2, 3

Answer

In your case, I'm assuming that the monotonic queue you're trying to obtain is increasing, so based on your given array {10, 7, 1, 2, 4, 3, 8}, at every iteration we would have:

10 => [10]
7 => [7]
1 => [1]
2 => [1, 2]
4 => [1, 2, 4]
3 => [1, 2, 3]
8 => [1, 2, 3, 8]

In conclusion, to answer your question:

am I supposed to have {1, 2, 3, 8} or just {3, 8}?

you're supposed to obtain {1, 2, 3, 8}.