Queue: A Missed java.util Class, Page 2

Second Approach

This approach aims to overcome the above mentioned performance problem by building the Queue class on the top of a LinkedList class since the deletion of the first element of the linked list will not result a shift in the remaining elements.

public class Queue2 extends LinkedList
{
	public Object enqueue (Object element)	
	{
		add (element);
		return element;
	}

	public Object dequeue ()
	{
		if (size()== 0)	
			throw new EmptyQueueException() ;
		return removeFirst();		
	}
}

A problem with this approach arises because of inheritance. The user of this Queue2 class can invoke some inherited methods like addFirst or getLast causing unwanted behaviors of the Queue class.

Third Approach

In this approach object composition will be used instead of inheritance. In general, object composition should be favored over inheritance. It promotes smaller, more focused classes and smaller inheritance hierarchies. Most designers overuse inheritance, resulting in large inheritance hierarchies that can become hard to deal with. A design based on object composition will have fewer classes, but more objects.

public class Queue 
{

	private LinkedList items;

	public Object enqueue (Object element)
	{
		items.add (element);
		return element;
	}

	public Object dequeue () 
	{
		if (items.size()== 0)	
			throw new EmptyQueueException() ;
		return items.removeFirst();		
	}
}

This implementation results in a powerful and focused Queue class. However the developer has to explicitly hard code all the required interface (e.g. methods like size, empty, indexOf). The complete code of the third approach is available.

Download code

Related Links

• Queue vs. Stack
  http://panastech.com/projects/Raj_Gaire/QandS/QueAndStack.htm
• Java Utility Package
  Sun: http://java.sun.com/j2se/1.4.2/docs/api/java/util/package-summary.html
• Composition versus Inheritance
  Bill Venners: http://www.artima.com/designtechniques/compoinh.html
  Paul John Rajlich: http://brighton.ncsa.uiuc.edu/~prajlich/T/node14.html

About the author

Yasser EL-Manzalawy is a java programmer and instructor since 1998. He is currently an assistant Lecturer at the Systems & Computers Engineering Department, AZHAR University, Cairo. His Ph.D. research project aims to extend the Java language for agent based systems.