The Java Collections Framework - Queues

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection types: Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

---

A queue is an ordered collection of elements in which only the "top" element can be accessed. When the top element is removed, or popped, the next element is revealed. The order in which the queue's elements are arranged depends upon the type of queue. Also, note that the term push is used to refer to an element being added to a queue.

• A FIFO (first in, first out) queue orders its elements according to how recently they were added to the queue--elements that were pushed first will be popped first.
• A LIFO (last in, first out) queue, also known as a stack, is the opposite of a FIFO queue--elements that were pushed first are popped last.
• There's also a priority queue, in which each element has a priority associated with it. The elements with the highest priorities are popped first.

A dequeue (double-ended queue) allows the programmer to push and pop elements from the bottom of the queue as well as from the top.

"Exception vs. special return value" convension

The Java Collections Framework has a number of implementations for different types of queues (all inheriting from the Queue interface). They all follow a special convension: for each operation that you can perform on the queue, there are two methods. Each method does the same thing, but they differ in the way in which they handle edge cases. One method will throw an exception, while the other will return a special value. Here are some examples of these kinds of methods from the Queue interface.

• add() - pushes an element on the queue, throwing an IllegalStateException if the queue is full.
• offer() - pushes an element on the queue, returning false if the queue is full.
• remove() - pops the next element off the queue, throwing a NoSuchElementException if the queue is empty.
• poll() - pops the next element off the queue, returning null if the queue is empty.

Example

Here's an example of how to program a queue in Java. This program simulates a drive-thru window at a fast-food restaurant. Customers place their orders at the drive-thru window and then the kitchen makes their food. The kitchen makes the meals in the same order in which they were received, so it is a FIFO queue (if you are the first car in line, you will be the first to receive your order).

I use a BlockingQueue, which extends the Queue interface. It provides the ability to block the method call if you try to pop from an empty queue or push to a full queue. I use the take() method to pop the next element off the queue. If the queue is empty, then it waits until an element is pushed onto the queue before executing the next line of code.

The BlockingQueue imlpementation I use is the ArrayBlockingQueue, which requires that a max queue size be defined. In the case of my drive-thru simulator, this is the maximum number of cars that can fit into the driveway. I use the offer() method to push orders onto the queue. If this method returns false then it means that the driveway is full of cars (the queue is full). The would-be customer then has to drive away and find someplace else to get their food (nothing is pushed to the queue).

import java.text.MessageFormat;
import java.util.*

/**
 * Drive-thru simulator for a fast-food restaurant.
 * @author Mike Angstadt - http://www.mangst.com
 */
public class DriveThru {
  private static Random rand = new Random();

  public static void main(String args[]) throws InterruptedException {
    //the number of cars that can fit in the driveway
    int drivewaySize = 5;

    //the food orders are placed in a FIFO queue with a max capacity
    BlockingQueue<String> orders = new ArrayBlockingQueue<String>(drivewaySize);

    //the drive-thru window takes orders from the customers and pushes those orders onto the queue
    DriveThruWindow driveThruWindow = new DriveThruWindow(orders);
    driveThruWindow.start();

    //the kitchen pops the orders off the queue
    Kitchen kitchen = new Kitchen(orders);
    kitchen.start();
  }

  private static class Kitchen extends Thread {
    private BlockingQueue<String> orders;

    public Kitchen(BlockingQueue<String> orders) {
      this.orders = orders;
    }

    @Override
    public void run() {
      int orderNum = 0;
      while (true) {
        try {
          //get the next order
          //if the queue is empty, then wait until an element is pushed onto it
          String order = orders.take();

          //make the food
          System.out.println("Order " + orderNum + ": Making order \"" + order + "\"...");
          Thread.sleep(rand.nextInt(9000) + 1000); //sleep for 1-10 seconds
          System.out.println("Order " + orderNum + ": Order \"" + order + "\" finished.");
          orderNum++;
        } catch (InterruptedException e) {
          break;
        }
      }
    }
  }

  private static class DriveThruWindow extends Thread {
    private List<MenuItem> menu = new ArrayList<MenuItem>();
    private int orderNum = 0;
    private BlockingQueue<String> orders;

    public DriveThruWindow(BlockingQueue<String> orders) {
      this.orders = orders;

      //create the menu
      MenuItem menuItem = new MenuItem("Quarter-pounder", new String[] { "cheese", "tomatoes", "onions", "pickles" }, "{0} with {1}");
      menu.add(menuItem);
      menuItem = new MenuItem("coke", new String[] { "Small", "Medium", "Large" }, "{1} {0}");
      menu.add(menuItem);
      menuItem = new MenuItem("chicken nuggets", new String[] { "6", "10", "20" }, "{1}-piece {0}");
      menu.add(menuItem);
      menuItem = new MenuItem("Apple pie");
      menu.add(menuItem);
    }

    @Override
    public void run() {
      while (true) {
        //wait for the next car
        try {
          Thread.sleep(rand.nextInt(6000) + 1000); //sleep for 1-7 seconds
        } catch (InterruptedException e) {
          break;
        }

        //get the customer's order
        int index = rand.nextInt(menu.size());
        String order = menu.get(index).generate();

        //push the order onto the queue
        boolean inserted = orders.offer(order);
        if (inserted) {
          System.out.println("Order " + orderNum + ": Car placed order for \"" + order + "\".");
          orderNum++;
        } else {
          System.out.println("Driveway full...customer lost!");
        }
      }
    }
  }

  private static class MenuItem {
    private final String name;
    private final String[] modifiers;
    private final String format;

    public MenuItem(String name) {
      this(name, null, null);
    }

    public MenuItem(String name, String[] modifiers, String format) {
      this.name = name;
      this.modifiers = modifiers;
      this.format = format;
    }

    public String generate() {
      if (format == null) {
        return name;
      } else {
        int modifier = rand.nextInt(modifiers.length);
        return MessageFormat.format(format, name, modifiers[modifier]);
      }
    }
  }
}