Java ArrayDeque Examples

Use ArrayDeque to push, pop and peek at elements. An ArrayDeque works as a queue and a stack.

ArrayDeque. This is an optimized stack and queue. We often use ArrayDeque in parsers and caches. Its performance is excellent. 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.

Consider this program. We add three Integers (10, 500 and 1000) to the ArrayDeque. Please notice how we specify the type in the ArrayDeque—on the right side, the type Integer is inferred.

Push: This adds an element to the front (or the top) of the ArrayDeque. The type must be matched that specified in the declaration.

Peek: Returns the frontmost (or topmost) element in the collection. It does not affect the ArrayDeque's contents.

Pop: This removes the topmost element of the ArrayDeque and returns it. Pop() throws an exception if empty.

Java program that uses ArrayDeque 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); } } Output 1000 1000 500

Add, looping. 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.

For: The program loops over all the elements in the ArrayDeque with a for-each loop. No index is needed.

For

Java program that uses add, loops 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); } } } Output caterpillar dinosaur bird

IsEmpty, size, clear. An ArrayDeque that has no elements must be specially handled. We can check isEmpty before calling pop() to avoid exceptions.

Size: This integer always equals 0 when the ArrayDeque is empty. The size() changes as elements are added and removed.

Clear: This removes all the elements in the ArrayDeque. To restart an algorithm, clear() is a simpler option than calling pop() many times.

Java program that uses isEmpty, size and clear 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()); } } Output false 4 true 0

Wiki parser. 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: We use an enum called Tag. We push our tags (None, Italics, Bold) to the ArrayDeque to help with parsing.

StringBuilder: We use a StringBuilder to build up a result from the parser. In the end this holds finished HTML.

StringBuilder

Loop: In the loop, we see if the char is a star or underscore. And we manipulate the ArrayDeque based on its current contents.

Tip: This not complete code. But it shows how we use an ArrayDeque to manage a parser's state: we know whether to open or close a tag.

Java program that uses ArrayDeque for wiki parser 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(""); } else { codes.push(Tag.Italics); builder.append(""); } } else if (value == '_') { // Close bold if on stack, otherwise open it. if (codes.peek() == Tag.Bold) { codes.pop(); builder.append(""); } else { codes.push(Tag.Bold); builder.append(""); } } else { // Append other characters. builder.append(value); } } // Display our results. System.out.println(wiki); System.out.println(builder); } } Output How are *you my _friend_*? How are you my friend?

Benchmark, ArrayDeque. What is the performance difference between ArrayDeque and Stack? The Stack is an older version of ArrayDeque.

Version 1: This version of the code creates and adds ten values to an ArrayDeque.

Version 2: Here we create a Stack, and push() elements to it. We perform the same number of operations as version 1.

Result: The ArrayDeque can be populated with 10 integers many times faster than a Stack. ArrayDeque should always be preferred.

Java program that times ArrayDeque and Stack 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); } } Output 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.Stack

ArrayDeque is important. It 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java ArrayDeque Examples

Related Links:

.Net

Java

Related Links