Queues in Java

In this lesson, you'll learn another abstract data type called a Queue, which is basically the same as a Stack.

Stack and Queue in Java

The only difference is that a Queue employs a "Last-In-Last-Out" (LILO) functionality (you can also call this "First-In-First-Out" or FIFO).

Much like a queue (or line) that you would get into at your favorite coffee shop or cafe, if you're the last one in that queue (line), you're going to be the last one out of that queue.

As a reminder, a Stack employs the opposite functionality: it implements LILO (aka FIFO) like a stack of plates on the counter. The first plate you place down (at the bottom of the stack) will be the last one you can retrieve from that stack.

Big O Complexity

All of the methods of accessing, inserting, removing, and searching are the same for queues as they are for stacks.

Therefore, the Big-O notation is also the same: You insert and remove at O(1) and access and search at O(n).

How Does a Queue Work

A Queue simply enforces a particular set of behaviors. For instance, if the underlying data structure is an Array, you simply enforce the idea that a user can ONLY insert elements onto the bottom (aka the end) of the queue and users can ONLY remove elements from the top (aka front) of the queue.

Queues, generally speaking, are limited access data structures, meaning you limit access to the underlying data. It is NOT random access. Typically, you cannot get a plate out of the middle of the queue; you can only add elements to the end of the queue and remove elements from the front of the queue.

Java Queue Implementations

As with all other primary data structures, Java provides its own built-in implementation(s) of the Queue. In the case of the Queue, which Java implements as an interface, there are actually several implementations of the Queue class.

Common Queue Implementations

Below is a list of the common implementations of the Queue class that come built into Java.

As mentioned in the previous section, LinkedList implements the Queue interface, providing first in, first out (FIFO) queue operations for add(), poll(), and so on.

The queue retrieval operations — poll(), remove(), peek(), and element() — access the element at the head of the queue.

General-Purpose Queue Implementations

The general purpose queue is what you've learned so far: an underlying abstract data structure like Array or LinkedList that applies the FIFO functionality.

PriorityQueue 

The PriorityQueue class is a queue that orders its elements according to their priority, a value that is specified at construction time. The ordering can be the elements' natural ordering or an order that is imposed by an explicit comparison.

As a result of implementing the optional methods from the Collection and Iterator classes, the PriorityQueue isn't guaranteed to traverse its elements in any particular order. One way to fix this is using Arrays.sort(pq.toArray()).

The head of a PriorityQueue is the least element of the specified ordering and if there is a tie, then it is broken arbitrarily.

Concurrent Queue

The java.util.concurrent package contains a set of synchronized Queue interfaces and classes, which means ----- Below is a brief explanation of one of the commonly used concurrent queues:

• BlockingQueue extends Queue with operations that wait for the queue to become nonempty when retrieving an element and for space to become available in the queue when storing an element. This interface is implemented by the following classes: (please note you'll come back to the meaning of "heap".)
  • LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
  • ArrayBlockingQueue — a bounded FIFO blocking queue backed by an array
  • PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
  • DelayQueue — a time-based scheduling queue backed by a heap
  • SynchronousQueue — a simple rendezvous mechanism that uses the BlockingQueue interface

Priority Queue Example

Here's an example of a PriorityQueue in action:

import java.util.*;

public class Main {
  public static void main(String[] args) {
    // a priority queue orders it's elements by their natural order
    // by default with Strings this will be alphabetically
    PriorityQueue<String> myQueue = new PriorityQueue();
    // add elements to the Queue
    myQueue.add("java");
    myQueue.add("provides");
    myQueue.add("many");
    myQueue.add("queue");
    myQueue.add("implementations");
  
    // peek at the "top/front" of the Queue
    System.out.println(myQueue.peek());
  
    // demonstrate contains() method
    boolean hasJava = myQueue.contains("Queue");
    System.out.println("Contains \"Queue\"? -> " + hasJava);
    System.out.println();

    // remove an element from the front of the Queue
    String r1 = myQueue.remove();
    System.out.println(r1);

    // Retrieves, but does not remove, the head of this queue.
    String e1 = myQueue.element();
    System.out.println(e1);

    // iterate over Queue and print out elements
    for(String s : myQueue){
      System.out.println(s);
    }

    // clear the Queue
    myQueue.clear();
  }
}

Summary: Java Queues

• A Queue is an abstract data type in Java
• Queues and stacks are essentially the same
• The only difference from a Stack is that a Queue operates with the First in First Out (FIFO) functionality, also known as Last in Last Out (LILO)
• Like stacks, queues are often built on top of an Array or a LinkedList

Big O Notation of a Queue

• Best Case (Insert & Remove): O(1)
• Worst Case (Access & Search): O(n)

Java Queue Implementations

• Java has several pre-built implementations of the Queue class
• This lesson also provides an example PriorityQueue

Common Implementations

• General-Purpose Queue
• PriorityQueue 
• Concurrent Queue