In this post I would be discussing implementation of an array based queue and linked list based queue in Java programming language. Wikipedia defines Queue as:
Queue (FIFO-First In First-Out)
In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.
In Java, a queue can be implemented using an array or as a linked list representation using reference variables and objects. Array based arrays are good for conceptual clarity but unlike linked list implementation they are not truly dynamic because the size of an array must be declared at the time of creation/memory allocation. Once created an array can neither shrink nor expand and hence, is not dynamic in true sense of the word. In linked list representation the nodes are allocated/unallocated as and when the need arises and are truly dynamic, however, there is some memory overhead due to the use of reference variables. Please note that in real life scenarios the number of data items in each node is usually more than one and thus, the overheads are not significant.
Handling of overflow and underflow conditions
This is one of those topics where I prefer my own implementation over the implementation given in most textbooks. The reason being that most textbooks for ISC do not use exception handling for signalling overflow and underflow conditions even though exception handling is in the ISC syllabus. I do not subscribe to the idea of displaying a message on the console when overflow or underflow condition is encountered because in that case the programmer who is using the methods ( that is enqueue( ) or dequeue( ) methods ) has no control over the flow of control once the abnormal condition occurs. Queues are used as a means to an end and is not an end in itself. It should be obvious, that once the memory is used up or there are no nodes left when the user is trying to pop a node, there is no point in continuously displaying error messages which are displayed on the screen. The code segment using the push or pop methods cannot see the messages!
The process of creating custom exceptions for overflow and underflow is neither complex nor cumbersome. I would be creating two exception classes for the purpose of this post, one for overflow and the other for underflow exception by the name OverflowException and UnderflowException respectively.
In order to create an exception one needs to create a class and extend it from either Exception class or RuntimeException class. When we extend from Exception class out exception is a checked exception meaning that we must catch ( use try…catch block) or declare that an exception can be thrown (use throws where the methods are being used). When we extend from RuntimeException, the exception is an unchecked exception meaning there is no need to use try-catch block or use throws.
Let us understand the distinction between extending from Exception or RuntimeException with the help of something which everyone probably know. When we use readLine() method of BufferedReader class we either use try-catch or declare the enclosing function as throws IOException- the underlying idea is that IOException is a checked exception. The compiler would check that we are doing something to handle the exception. When we are using the division operator, an exception ArithmeticException may be thrown, if the divisor is zero; but we never use try-catch or throws for the same because it’s an unchecked exception. Now, I would be using RuntimeException in this post primarily to decrease code clutter and keep things simple. Overflow and underflow classes would be as follows:
class OverflowException extends RuntimeException{
public OverflowException(){
super("Overflow exception. No memory left");
}
}
class UnderflowException extends RuntimeException{
public UnderflowException(){
super( "Underflow exception. No nodes left" );
}
}
For our purpose, the above code would be functional even if we remove the highlighted lines. The purpose of the constructor is to pass the message ( “Overflow exception. No memory left” or “Underflow exception. No nodes left” ) to the base class constructor so that it can be displayed if and when the exception is thrown. Students are advised to run the code once after removing the highlighted code to see the effect. When we need to throw an exception, we would create an object of the required class and throw it using the keyword throw.
An array based Queue in Java
class Queue{
private int data[], front, rear;
public Queue(){
data = new int[ 10 ];
front = rear = -1;
}
public Queue( int size ){
if( size <= 0 )
throw new IllegalArgumentException();
data = new int[ size ];
front = rear = -1;
}
public boolean isEmpty(){
return front == -1;
}
public void enqueue( int data ){
if( rear == this.data.length-1 ){
throw new OverflowException();
}
this.data[ ++rear ] = data;
if( front == -1 ) front = 0;
}
public int dequeue( ){
if( isEmpty() ){
throw new UnderflowException();
}
int data = this.data[ front++ ];
if( front > rear ){
front = rear = -1;
}
return data;
}
}
class OverflowException extends RuntimeException{
public OverflowException(){
super("Overflow exception. No memory left");
}
}
class UnderflowException extends RuntimeException{
public UnderflowException(){
super( "Underflow exception. No nodes left" );
}
}
class QueueTest{
public static void main( String args[] ){
Queue q =new Queue();
for( int i = 1; i <=10 ; i++ ){
q.enqueue( i );
}
while( !q.isEmpty() ){
System.out.println( q.dequeue() );
}
}
}
In the above program we are using the array data to store the node data and the integer variables front and rear to hold the index positions of the current front and rear in the array respectively. There are two constructors, the default constructor would allocate an array of size 10 and the parametrized constructor would accept a size at the time of instantiation of the Queue object.
We are throwing an IllegalException in case the value is negative or zero as it arrays can only have positive size. The value of front and rear is initialized to -1 in the beginning, since array index of an array starts from 0, the value of -1 would indicate empty queue.
The value of front would increase on dequeue operation and the value of rear would increase on enqueue operation. If the value of front exceeds the maximum subscript value (data.length-1) of the data array overflow would result and if dequeue operation is attempted when the queue is empty (top =1) then underflow would occur.
The main function simply enqueues values from 1 to 10 and then removes (dequeues) out element one by one till the queue is not empty. The output of all integers from 1 to 10 would indicate that the Queue is functioning properly.
The above implementation of an array based queue in java gives correct output but does not make optimal used of space in array. For example if we enqueue 10 elements, the entire array would be used, then if we dequeue 9 elements, all but the last element would be used. But note, that even now we cannot enqueue any element (even when the first nine elements of the array ‘data’ is free) because rear is at the last element of the array ‘data’, which is the condition of the full queue!
An array based Circular Queue in Java
As discussed in the preceding paragraph an array based queue does not make optimal usage of the space available in the array. To overcome the problem, circular queue is used. In circular queue the rear index variable moves to the front once it reaches the end if there is unused space in the beginning of the array, hence the name circular queue. The implementation of circular queue in Java is as follows:
class CircularQueue{
private int data[], front, rear;
public CircularQueue(){
data = new int[ 10 ];
front = rear = -1;
}
public CircularQueue( int size ){
data = new int[ size ];
front = rear = -1;
}
public boolean isEmpty(){
return front == -1;
}
public void enqueue( int data ){
if( ( front == 0 && rear == this.data.length-1 ) || rear == front - 1){
throw new OverflowException();
}
if( rear == -1 ){ // first element
front = rear = 0;
}else if( rear == this.data.length-1 ){
rear = 0;
}else rear++;
this.data[ rear ] = data;
}
public int dequeue( ){
if( isEmpty() ){
throw new UnderflowException();
}
int data = this.data[ front ];
if( front == rear ){ // last element removed
front = rear = -1;
}else if( front == this.data.length-1){ // front reached the last element
front = 0;
}else front++;
return data;
}
}
class OverflowException extends RuntimeException{
public OverflowException(){
super("Overflow exception. No memory left");
}
}
class UnderflowException extends RuntimeException{
public UnderflowException(){
super( "Underflow exception. No nodes left" );
}
}
class CircularQueueTest{
public static void main( String args[] ){
CircularQueue q =new CircularQueue();
for( int i = 1; i <=10 ; i++ ){
q.enqueue( i );
}
for( int i = 1; i <=5 ; i++ ){
System.out.println( q.dequeue() );
}
System.out.println("-");
for( int i = 1; i <=5 ; i++ ){
q.enqueue( i );
}
while( !q.isEmpty() ){
System.out.println( q.dequeue() );
}
}
}
A Linked List based Queue in Java
class Queue{
private class Node{
int data;
Node next;
public Node( int data ){
this.data = data;
}
}
private Node front, rear;
public Queue(){
front = rear = null;
}
public boolean isEmpty(){
return front == null;
}
public void enqueue( int data ){
try{
Node newNode = new Node( data );
if( isEmpty( ) ){
front = rear = newNode;
}else{
rear.next = newNode;
rear = newNode;
}
}catch( OutOfMemoryError e ){
front = null;
rear = null;
throw new OverflowException( );
}
}
public int dequeue( ){
if( isEmpty() ){
throw new UnderflowException();
}
int data = front.data;
front = front.next;
if( front == null ){
rear = null;
}
return data;
}
}
class OverflowException extends RuntimeException{
public OverflowException(){
super("Overflow exception. No memory left");
}
}
class UnderflowException extends RuntimeException{
public UnderflowException(){
super( "Underflow exception. No nodes left" );
}
}
class CircularQueueTest{
public static void main( String args[] ){
Queue q =new Queue();
for( int i = 1; i <=10 ; i++ ){
q.enqueue( i );
}
for( int i = 1; i <=5 ; i++ ){
System.out.println( q.dequeue() );
}
System.out.println("-");
for( int i = 1; i <=5 ; i++ ){
q.enqueue( i );
}
while( !q.isEmpty() ){
System.out.println( q.dequeue() );
}
}
}
In the above program the class Node is modelling a node and encapsulates the two parts of the node-the data part and the next part. The initialization of node is done through the Node constructor. Since the creation of node is always followed by storing of the node value I have used a constructor instead of a dedicated function for storing data in the node.
The data member front is a reference variable holds the reference of the front node. If the value of front is null it means that the queue is empty. The data member rear is a reference variable holds the reference of the last node. The value of front is modified when an element is removed(dequeue) and the value of rear is modified when an element is added (enqueue), however, if the last node is being removed or added both front and rear is modified.
The enqueue function deserves some explanation particularly the exception handling part. When we allocate memory using the operator new there is possibility that it would fail if there is no heap memory left. In that case JVM would throw OutOfMemoryError. This is actually our overflow condition. Notice that in the catch block we are assigning top to null. This is important because when all memory is exhausted we cannot do anything, not even display a message because println() function also requires some memory to execute. Now, since all the memory is exhausted it is obvious that we cannot continue. We must free some memory so that we can recover from memory crises and take some alternative action. As soon as we assign null to front. The block of memory which front was referring to would be eligible for garbage collection. This implies that JVM would free that block of memory. As soon as this happens there would be no one referring to the second node now because the next part of the fist node is now gone. Thus, the memory allocated to the second node would also be free. This would go on till all the memory occupied by all the nodes is free.
The underflow condition is pretty straight forward and occurs when we try to remove a node from an empty queue.
The main function simply enqueues some values in the queue and then removes (dequeues) out element one by one till the queue is not empty.
Creating the underflow condition
Underflow condition can easily be created by modifying the main function of the QueueTest as follows:
class QueueTest{
public static void main( String args[] ){
Queue q = new Queue();
System.out.println( q.dequeue( ) );
}
}
Creating the overflow condition
Overflow condition can be created by modifying the main function of the QueueTest as follows:
class QueueTest{
public static void main( String args[] ){
Queue q = new Queue();
while(true){
q.enque( 1 );
}
}
}
The above code would repeatedly add new nodes till all the memory is exhausted and would eventually lead to overflow condition.