April 17, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Queue: A Missed java.util Class

  • January 8, 2004
  • By Yasser EL-Manzalawy
  • Send Email »
  • More Articles »

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).



Page 1 of 2



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel