arrayedqueueuos.java

国外的数据结构与算法分析用书

/* ArrayedQueueUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.dispenser;

import dslib.base.*;
import dslib.exception.*;

/**	A bounded implementation of a queue that uses an array to store the items.
	Item refers to the item at the front of the queue that can be
	deleted.  There are also methods to insert items and check for empty. */
public class ArrayedQueueUos implements DispenserUos, BoundedUos
{
	/* 	Use the array in a circular fashion with items in locations 
		front, front + 1, ..., next - 1 (all mod capacity()). */
		
	/**	The internal representation of the queue. */
	protected Object[ ] rep;

	/**	Position of front item. */
	protected int front;

	/**	Position for next insertion. */
	protected int next;

	/**	Number of items in the queue. */
	protected int count;

	/**	Construct a new queue with specified capacity. <br>
		Analysis: Time = O(1) 
		@param length capacity of the queue */
	public ArrayedQueueUos(int length)
	{
		rep = new Object[length];
		count = 0;
		front = 0;
		next = 0;
	}

	/**	Is the queue empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return count == 0;
	}

	/**	Is the queue full?. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return count() == capacity();
	}

	/**	Is there an item in the queue?. <br>
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !isEmpty();
	}

	/**	The front item in the queue. <br>
		Analysis: Time = O(1) <br> 
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws NoCurrentItemUosException 
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item from an empty queue.");

		return rep[front];
	}

	/**	Number of items in the queue. <br>
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	Number of items the queue can hold. <br>
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}

	/**	Inserts x at the next location in the queue. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isFull()
		</ul>
		@param x new item to be inserted */
	public void insert(Object x) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full queue");

		rep[next] = x;
		count++;
		next = (next+1) % capacity();
	}

	/**	Deletes the first item in the queue. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item from an empty queue.");

		count--;
		front = (front+1) % capacity();
	}

	/**	Remove all items from the queue. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rep = new Object[capacity()];
		count = 0;
		front = 0;
		next = 0;
	}

	/**	String representation of the contents of the queue. <br>
		Analysis: Time = O(n), where n = number of items */
	public String toString()
	{
		String result = "Queue front: ";
		int i = front;
		int c = 0;
		while (c != count)
		{
			result +=  rep[i].toString() + " ";
			i = (i+1) % capacity();
			c++;
		}
		return result;
	}

	/**	A shallow clone of this object. <br>
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			/*	Should not occur: this is a ContainerUos that implements Cloneable */ 
			e.printStackTrace();
			return null;
		}
	}
}