Queues: ordered collection of items such that items are inserted and removed only from opposite ends. Insert at rear, remove from front. Implements FIFO.

Liken to waiting line.

Textbook ObjectQueue class is focus. See author's documentation at

http://www.cs.colorado.edu/~main/docs/edu.colorado.collections.ObjectQueue.html

Author also provides a family of queue classes, one for each primitive type. As an example, see author's documentation for IntQueue class at

http://www.cs.colorado.edu/~main/docs/edu.colorado.collections.IntQueue.html

Author provides separate classes for array and linked-list implementation. The linked list implementations are named by replacing "...Queue" in class name with "...LinkedQueue".

Java does not provide a class specifically for queues! Java does provide a List interface (not to be confused with the java.awt.List class which is used for scrolling lists of selectable text items). Several java classes directly implement the List interface: ArrayList, LinkedList, Vector.

Java documentation suggests that java.util.LinkedList is a reasonable choice for implementing queues, because it allows items to be inserted or removed from either end of the list. See Sun's documentation at http://java.sun.com/j2se/1.3/docs/api/java/util/LinkedList.html.

Java documentation does not address the issue of using java.util.ArrayList for implementing queues. It can be done, but must be done carefully. We will study array implementation of queues in greater depth.

Queues are used extensively in operating systems, in networks software, and in simulation programming.

• Every device on a computer system operates at different speeds.
• They also need to communicate with each other, passing commands and data back and forth.
• To require completely synchronous operation is inefficient because it requires the sender and receiver to operate at the slower speed of the two.
• When devices need to communicate with each other, OS provides buffers to hold information.
• These buffers are queues. Sender places information in one end and receiver removes it from the other. What happens when buffer becomes empty, or full?

Part I: standard stuff

• There are two constructors, one of which allows user to specify capacity. This implies array implementation.
• There are several methods related to the array implementation: getCapacity, ensureCapacity, trimToSize. Although their specification is the same as we've seen in the past, the implementation of the last two is quite different and interesting.
• There is a clone method.
• There is a boolean isEmpty method.
• There is an int size method.

Part II: interesting stuff

• public Object getFront(), removes and returns front item from queue. Assumes the queue is non-empty; throws an acception if it is empty. This is known generically as the "dequeue" operation.
• public void insert(Object item), adds this item to the rear of the queue. This is known generically as the "enqueue" operation.

Instance variables:

• data, an array of Objects for the queue itself
• front, an integer index for element containing next item to be removed
• rear, an integer index for element containing last item inserted
• manyItems, an integer counter of the number of items in the queue

How should getFront and insert operate?

• For non-empty queue, getFront returns data[0]then shifts remaining items left one slot.
• insert simply does the assignment data[++rear] = item;

What is the problem with Implementation 1? GetFront is not time-efficient.

• For non-empty queue, getFront simply returns data[front++];
• insert simply does the assignment data[++rear] = item; If rear was equal to data.length-1 coming in, call ensureCapacity first to increase array size

What is the problem with implementation 2? Is not space efficient.

Implementation candidate 3 uses concept of circular array (to use space efficiently):

For insert:

• if manyItems==data.length then call ensureCapacity to make array bigger
• if rear==data.length-1 then "increment" rear to 0. (e.g. increment is done modulo data.length) instead of regular increment. (see private method nextIndex)

For getFront:

• if manyItems==0 throw exception
• if front==data.length-1 then "increment" front to 0 (e.g. increment is done modulo data.length) instead of regular increment.

How would you implement ensureCapacity?

Note: full array does not imply that front==0 and rear==data.length-1!

It does imply that if front==0 then rear==data.length-1 else rear==front-1.

Instance variables:

• front, a reference to node containing next item to be removed
• rear, a reference to node containing last item inserted
• manyItems, an integer counter of the number of items in the queue

Will a singly-linked list suffice?

Why do you not need preRear (e.g. reference to node that precedes rear)?

Given

class Node
{
	public Object data;
	public Node next;
}

How would you implement insert?

How would you implement getFront?

Each item has associated priority. It should be selected only if no items of higher priority exist and all previously inserted items of same priority have been selected (e.g. goes to rear of line for its priority).

Two approaches:

1. an array of queues, one per priority level. Insert is easy, but getFront requires search for highest priority queue that is non-empty.

2. a single queue with enhanced insert method to place new item just prior to first item having lower priority (e.g. after the last item having same priority level). GetFront stays the same. You want linked-list implementation due to insertion in middle of queue.

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )