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.
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 anIllegalStateException
if the queue is full.offer()
- pushes an element on the queue, returningfalse
if the queue is full.remove()
- pops the next element off the queue, throwing aNoSuchElementException
if the queue is empty.poll()
- pops the next element off the queue, returningnull
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]); } } } }