Deques in Java
JDK is shipped with the Deque interface as well as many useful implementing classes, including ArrayDeque, LinkedList. In this section, we use ArrayDeque
as the running example, which is a resizable-array implementation of the Deque
interface. Deque
defines methods to access the elements at both ends of the deque.
Deque<String> deque = new ArrayDeque<>();
deque.offerLast("structures");
deque.offerLast("is");
deque.offerFirst("data");
deque.offerLast("fun");
assert Objects.equals(deque.pollFirst(), "data");
assert Objects.equals(deque.peekLast(), "fun");
The implementation based on circular arrays by yourself is left as an exercise.
If you need deques in your project, please choose one of the implementing classes from JDK, instead of designing a new one from the scratch.
Application: number of recent calls
This application is from leetcode, and readers shall check the question description by themselves.
As for this problem, one feasible algorithm is to use ArrayDeque
:
import java.util.ArrayDeque;
import java.util.Deque;
public class RecentCounter {
private final Deque<Integer> data;
public RecentCounter() {
data = new ArrayDeque<>();
}
public int ping(int t) {
while (!data.isEmpty() && (t - 3000) > data.peekFirst()) {
data.pollFirst();
}
data.offerLast(t);
return data.size();
}
}