The Java SE 6 Deque

I feel a little disappointment when I occasionally hear fellow Java developers make statements like this: "Java 6 doesn't really provide all that much." My experience with Java SE 6 has been very different and I find myself missing many of its features when I must use an earlier version of Java. While it is true that JDK 1.4 and J2SE 5 each introduced several significant language and syntax enhancements, Java SE 6 has provided many of its own highly useful new features as well. In this blog entry, I look at a feature that I don't use often, but is very nice to have available when I need it. I will be looking at the Java SE 6 additions to the Java Collections Framework of the Deque and the interfaces that extend it and classes that implement it.

The Deque (typically pronounced "deck" rather than "de-queue") interface supports the concept of a double-ended queue (and is not related to dequeue used to indicate removal from a queue). Because the double-ended queue supports addition or removal of elements from either end of the data structure, it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). J2SE 5 introduced a Queue interface and the Deque interface extends this interface. Note that a Vector-based Stack class has been present since JDK 1.0, but the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack as well.

The Deque interface is extended by the concurrency-supporting interface BlockingDeque and is implemented by classes LinkedBlockingDeque (introduced in Java SE 6), LinkedList (available since JDK 1.2, but now implements Deque), and ArrayDeque (introduced in Java SE 6). For this blog entry, I will demonstrate using one Deque instance as a queue and one Deque instance as a stack using ArrayDeque for both. ArrayDeque is not thread-safe and does not allow for elements of the data structure to be null (a recommended but not required condition of Deque implementations and uses).

package dustin.deque;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Example of using an implementation of the Deque interface that was added in
 * Java SE 6.  In particular, this example uses the ArrayDeque implementation
 * to implement a queue and a stack.  This example is intended to be used for
 * the blog "Dustin's Software Development Cogitations and Speculations" at
 * <a href="http://marxsoftware.blogspot.com/">http://marxsoftware.blogspot.com/</a>.
 */
public class MainDequeExample
{
   /** Deque implementation used as a queue. */
   private Deque queue = new ArrayDeque();

   /** Deque implementation used as a stack. */
   private Deque stack = new ArrayDeque();

   /**
    * Demonstrate use of Deque as a queue.
    */
   public void showOffDequeAsQueue()
   {
      setUpQueue();
      System.out.println(
           "The two elements that will be first out of this queue are "
         + this.queue.remove() + " and " + this.queue.remove() + ".");
   }

   /**
    * Set up Deque to be used as a queue by adding several prime integers to it.
    */
   private void setUpQueue()
   {
      this.queue.clear();
      this.queue.add(1);
      this.queue.add(3);
      this.queue.add(5);
      this.queue.add(7);
      this.queue.add(11);
      this.queue.add(13);
      this.queue.add(17);
      this.queue.add(19);
   }

   /**
    * Demonstate use of Deque as a stack.
    */
   public void showOffDequeAsStack()
   {
      setUpStack();
      System.out.println(
           "The two elements that will be first out of this stack are "
         + this.stack.pop() + " and " + this.stack.pop() + "." );
   }

   /**
    * Set up Deque to be used as a stack by adding several prime integers to it.
    */
   public void setUpStack()
   {
      this.stack.clear();
      this.stack.push(1);
      this.stack.push(3);
      this.stack.push(5);
      this.stack.push(7);
      this.stack.push(11);
      this.stack.push(13);
      this.stack.push(17);
      this.stack.push(19);
   }

   /**
    * Demonstrate that a Deque can be populated like a queue, but have its
    * elements retrieved like a stack.
    */
   public void showOffMixedDequeWithPopulatedQueue()
   {
      setUpQueue();
      System.out.println(
           "The two elements that will be first out of this queue accessed like "
         + "a stack are " + this.queue.pop() + " and " + this.queue.pop() + ".");
   }

   /**
    * Demonstrate that a Deque can be populated like a stack, but have its
    * elements retrieved like a queue.
    */
   public void showOffMixedDequeWithPopulatedStack()
   {
      setUpStack();
      System.out.println(
           "The two elements that will be first out of this stack accessed like "
         + "a queue are " + this.stack.remove() + " and " + this.stack.remove()
         + "." );
   }

   /**
    * Main function for executing the examples.
    *
    * @param arguments the command line arguments; none expected.
    */
   public static void main(final String[] arguments)
   {
      final MainDequeExample me = new MainDequeExample();
      me.showOffDequeAsQueue();
      me.showOffDequeAsStack();
      me.showOffMixedDequeWithPopulatedQueue();
      me.showOffMixedDequeWithPopulatedStack();
   }
}

When the code above is run, the output looks like that shown in the next screen snapshot.



As the example in this blog entry has shown, the Deque interface (and specifically the ArrayDeque class) provide a useful data structure for working with stacks and queues. Many more useful methods are supported in addition to those shown in the example. These include methods like addFirst, addLast, getFirst, getLast, removeFirst, and removeLast.

It is also worth noting that Java SE 6 added two methods to the Collections class. Of immediate interest is the addition of the Collections.asLifoQueue(Deque) method that accepts a Deque and, as the name suggests, returns a LIFO queue.

Java SE 6 has provided many useful conveniences and new features that improve developer productivity. These include Sun's Java SE 6 inclusion of JAXB, built-in annotations processing, VisualVM (as of Java SE 6 Update 7), Swing goodies such as SwingWorker, JMX and diagnostic tools, and other useful tools and APIs directly incorporated with Java. In addition, changes to the Java language itself such as String.isEmpty, Console, and Deque have also helped developers be more productive.