The standard java package, java.util, comes with a group of useful data structure classes (e.g. Stack, LinkedList, HashSet, and TreeSet classes). Unfortunately the Queue class is not implemented within this standard package. In this article we discuss three approaches to implement a Queue class.
Stack Vs. Queue
A stack is a data structure where you can only access the item at the top. With a computer stack, just like a stack of dishes, you add items to the top and remove them from the top. This behavior is known as LIFO (Last In, First Out). In contrast, a queue is a data structure in which elements are removed in the same order they were entered. This is often referred to as FIFO (First In, First Out).
The basic two operations of the stack are:
- Push: pushes a new element onto the top of the stack.
- Pop: removes the element at the top of the stack and returns that element. This operation may throw an exception when the stack is empty.
a. A stack with 4 elements b. The stack after pop operation
Figure 1: Pop operation for Stack class
Figure 1.a shows a stack with four elements, the brown element is the top of the stack. Figure 1.b shows the same stack after the execution of the pop operation, the brown element has removed and the green element became the top of the stack.
There are also two basic queue operations:
- Enqueue: inserts a new element at the rear of the queue.
- Dequeue: removes the element at the top of the queue and returns that element. This operation may throw an exception when the queue is empty.
The EmptyQueueException
This exception is thrown by Queue class methods to indicate an empty queue and it will be used with the following three discussed approaches.
public class EmptyQueueException extends RuntimeException
{
public EmptyQueueException() { }
}
First Approach
The first approach is similar to the one used for implementing java.util.Stack class. In this implementation the Queue1 class will extend the java.util.Vector class with the operations that allow a vector to be treated as a queue.
public class Queue1 extends Vector
{
public Object enqueue (Object element)
{
addElement (element);
return element;
}
public Object dequeue ()
{
int len = size();
if (len == 0)
throw new EmptyQueueException();
Object obj = elementAt(0);
removeElementAt (0);
return obj;
}
}
The enqueue method uses the inherited addElement method to add an object to the end of the vector. The dequeue method uses the inherited removeElementAt to remove the first stored object from the vector. In fact removing the top of the vector requires an additional task handled by the removeElementAt method. The remaining vector elements must be shifted up one position, see figure 2.
It should be noted that this implementation suffers a performance problem, especially with large number of queue elements. Figure 2 shows that each time dequeue method is called the first element of the Vector will be removed causing the remaining Vector elements to be shifted up one step. However, this is not the case with the Stack class, where each call to the pop method will remove the last element of the Vector and so there is no need to shift the remaining elements (see figure 1). In other words, although this approach is efficient for implementing the Stack class, it is not efficient for implementing the Queue class.
a. A queue with 4 elements b. After dequeue
Figure 2: Dequeue operation for first implementation (the remaining three elements had been shifted up one position).
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.
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.
