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.
CodePudding user response:
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}.