ArrayDeque
This is an optimized Java stack and queue. We often use ArrayDeque
in parsers and caches. Its performance is excellent, and it is versatile.
In a parser, state changes based on the tag last encountered. A stack, like ArrayDeque
, represents this logic—we deal with the "deepest" elements first.
We add 3 Integers (10, 500 and 1000) to the ArrayDeque
. We specify the type in the ArrayDeque
—on the right side, the type Integer is inferred.
Push()
adds an element to the front (or the top) of the ArrayDeque
. The type must be matched that specified in the declaration.ArrayDeque
's contents.ArrayDeque
and returns it. Pop throws an exception if empty.import java.util.ArrayDeque; public class Program { public static void main(String[] args) { // Create ArrayDeque with three elements. ArrayDeque<Integer> deque = new ArrayDeque<>(); deque.push(10); deque.push(500); deque.push(1000); // Peek to get the top item, but do not remove it. int peekResult = deque.peek(); System.out.println(peekResult); // Call pop on the Deque. int popResult = deque.pop(); System.out.println(popResult); // Pop again. popResult = deque.pop(); System.out.println(popResult); } }1000 1000 500
We do not need to use push to add elements: we can add add()
to add elements onto the end of the ArrayDeque
. This type can be used as a stack or a queue.
ArrayDeque
with a for
-each loop. No index is needed.import java.util.ArrayDeque; public class Program { public static void main(String[] args) { ArrayDeque<String> deque = new ArrayDeque<>(); // Use add on ArrayDeque. deque.add("caterpillar"); deque.add("dinosaur"); deque.add("bird"); // Loop over all the elements in the ArrayDeque. for (String element : deque) { System.out.println(element); } } }caterpillar dinosaur bird
IsEmpty
, size, clearAn ArrayDeque
that has no elements must be specially handled. We can check isEmpty
before calling pop()
to avoid exceptions.
Size
always equals 0 when the ArrayDeque
is empty. The size()
changes as elements are added and removed.ArrayDeque
. To restart an algorithm, clear()
is a simpler option than calling pop()
many times.import java.util.ArrayDeque; public class Program { public static void main(String[] args) { ArrayDeque<Double> doubles = new ArrayDeque<>(); // Add four elements to the ArrayDeque. doubles.push(50.25); doubles.push(100.40); doubles.push(120.25); doubles.push(150.50); System.out.println(doubles.isEmpty()); System.out.println(doubles.size()); // Clear all elements from the ArrayDeque. doubles.clear(); System.out.println(doubles.isEmpty()); System.out.println(doubles.size()); } }false 4 true 0
This example uses ArrayDeque
as a stack to parse a simple text language. The example "wiki" language uses stars and underscores to indicate italics and bold.
enum
called Tag. We push our tags (None
, Italics, Bold) to the ArrayDeque
to help with parsing.StringBuilder
to build up a result from the parser. In the end this holds finished HTML.char
is a star or underscore. And we manipulate the ArrayDeque
based on its current contents.ArrayDeque
to manage a parser's state: we know whether to open or close a tag.import java.util.ArrayDeque; import java.lang.StringBuilder; public class Program { enum Tag { None, Italics, Bold } public static void main(String[] args) { String wiki = "How are *you my _friend_*?"; ArrayDeque<Tag> codes = new ArrayDeque<>(); StringBuilder builder = new StringBuilder(); // Loop over the string. for (int i = 0; i < wiki.length(); i++) { char value = wiki.charAt(i); // Handle star or underscore characters. if (value == '*') { // Close italics if on stack, otherwise open it. if (codes.peek() == Tag.Italics) { codes.pop(); builder.append("</i>"); } else { codes.push(Tag.Italics); builder.append("<i>"); } } else if (value == '_') { // Close bold if on stack, otherwise open it. if (codes.peek() == Tag.Bold) { codes.pop(); builder.append("</b>"); } else { codes.push(Tag.Bold); builder.append("<b>"); } } else { // Append other characters. builder.append(value); } } // Display our results. System.out.println(wiki); System.out.println(builder); } }How are *you my _friend_*? How are <i>you my <b>friend</b></i>?
ArrayDeque
What is the performance difference between ArrayDeque
and Stack
? The Stack
is an older version of ArrayDeque
.
ArrayDeque
.Stack
, and push()
elements to it. We perform the same number of operations as version 1.ArrayDeque
can be populated with 10 integers many times faster than a Stack
. ArrayDeque
should always be preferred.import java.util.ArrayDeque; import java.util.Stack; public class Program { public static void main(String[] args) { long t1 = System.currentTimeMillis(); // Version 1: push 10 elements to ArrayDeque. for (int i = 0; i < 10000000; i++) { ArrayDeque<Integer> deque = new ArrayDeque<>(); for (int v = 0; v < 10; v++) { deque.push(v); } } long t2 = System.currentTimeMillis(); // Version 2: push 10 elements to Stack. for (int i = 0; i < 10000000; i++) { Stack<Integer> stack = new Stack<>(); for (int v = 0; v < 10; v++) { stack.push(v); } } long t3 = System.currentTimeMillis(); // ... Print benchmark results. System.out.println(t2 - t1); System.out.println(t3 - t2); } } 589 ms: ArrayDeque push 2664 ms: Stack push
Stack
This is an older collection. As the benchmark revealed, it has serious performance deficits. It exists for the benefit legacy programs. Avoid it.
ArrayDeque
is importantIt has clear optimizations over older collections like Stack
. And it is flexible—it provides both a stack and a queue.
With abstract
data types, we raise the conceptual level of our programs. With a stack, like ArrayDeque
, we logically push and pop elements, as in a parser.
In a queue, we can implement a help system with tickets. The older entries may be handled first, in FIFO order (first-in, first-out). No items are left too long with no action.