Page 1 of 1

Queues- Arrays and Linked Lists Rate Topic: -----

#1 karabasf  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

Posted 04 April 2012 - 05:32 AM

Level: Intermediate
Assumed knowledge: before you can start this tutorial, you're supposed to have knowledge of:
  • Interfaces
  • Arrays
  • Basic Java operations
  • Exceptions
  • Generics
  • Basic knowledge of Object Oriented Programming (Inheritance)


This tutorial will elaborate how an array can be used in order to implement a Queue. For this purpose, we will use a custom made Queue interface and two user defined exceptions to achieve our goal. (namely a First In, First Out based queue, implemented by an array)

Before we start slamming the keyboard, we need to define what operations it needs to support. Some basic operations of a queue are:

  • size, this returns an integer representing the size of the Queue
  • isEmpty, this returns a boolean to denote if the Queue is empty (or not)
  • enqueue, this is used to enqueue an element to the Queue (add an element to the Queue
  • dequeue, this is used to dequeue an element (remove the first element)
  • front, this returns (but does not remove) the first added element to the Queue


We will also define two custom exceptions for our ArrayQueue, namely:

  • EmptyQueueException, thrown when elements are accessed, while the Queue is empty
  • FullQueueException, thrown when an element is added, while the Queue is full


So, let's start of with defining our interface:

public interface Queue<E>{
	public int size();
	public boolean isEmpty();
	public void enqueue(E element);
	public E dequeue();
	public E front();
}


The next step is to define our exceptions. As these exceptions are runtime exceptions, we need to extend Javas RuntimeException class with our own exceptions. This results in:

public class FullQueueException extends RuntimeException{
	public FullQueueException(String err){
		super(err);
	}
}


And:

public class EmptyQueueException extends RuntimeException{
	public EmptyQueueException(String err){
		super(err);
	}
}

Of course, we could also add some basic constructors for our custom made exceptions, displaying a standard message when one of the exceptions is thrown. I leave this task up to the reader.

Now that we have defined our interface and our exceptions, we can start programming our ArrayQueue class. We will use the following variables:

  • int capacity: an integer representing the capacity of our ArrayQueue
  • int items: an integer representing the amount of items stored in our ArrayQueue
  • int front: an integer representing where the front element is located in the array
  • int rear: an integer representing where the rear element is located in the array
  • E[] elements: a generic array to store the elements in the ArrayQueue


We need to consider how this should work. First, of all, consider this situation:

Assume I already enqueued (added items to the queue) and dequeued (removed items), leading to the following situation:

[][][][][][F][I]....[I]...[R]....[][][][]
//F is front
//I is just an item
//R is rear
//[] are empty spots


What happens in the queue, is that when I enqueue, I add the element at the rear [R] and when I dequeue, I remove the item at the front [F].

Now, given this situation, if I continue to enqueue, this situation might arise:
[][][][][][F][I]....[I]...[R]
//F is front
//I is just an item
//R is rear
//[] are empty spots


Now [R] is at the end of my array. If I would add two more elements, I'd get an Array Out of Bound Exception. (as the index R would be lying outside the bounds of the array) But... My array is actually not full, I can still store items in front of [F]

So, what I can do, is wrap R around the array. In that case, the positions R and F can be calculated by the modulo operator:
r = (r+1) % N
f = (f+1) % N
N being the capacity of the array holding/representing the queue.


Now we get an idea what's going on, we can (finally) start programming our ArrayQueue.

Let's start with the constructors:
ArrayQueue<E> implements Queue<E>{
	int capacity;		//an integer representing the capacity of our ArrayQueue
	int items;			//an integer representing the amount of items stored in our ArrayQueue
	int front;			//an integer representing where the front element is located in the array
	int rear; 			//an integer representing where the rear element is located in the array
	E elements[]; 		//an generic array to store the elements in the ArrayQueue

	//Default constructor. If this is called, an ArrayQueue with capacity 10 is instantiated
	public ArrayQueue(){
		this.front = 0;
		this.rear = 0;
		this.capacity = 10;
		elements =  (E[]) new Object[this.capacity];
	}
	
	//Constructor to create an arrayqueue with a user defined size
	public ArrayQueue(int capacity){
		this.front = 0;
		this.rear = 0;
		this.items = 0;
		this.capacity = capacity;
		elements =  (E[]) new Object[this.capacity];
	}
}


So, what did we do here? We set the amount of items to 0 (as we didn't add anything), the capacity to either 10 or the user defined capacity (the amount of elements the array can store) and finally, we constructed an array based on generics.

The next step is to write the size() method and the isEmpty() method. We know that the Queue is empty when we don't have any items: thus if the variable items equals 0, then the array (and thus our Queue) is empty. This piece of code is fairly easy to implement:

//Return the amount of stored items in the ArrayQueue
public int size(){
	return this.items;
}

//Determine whether the ArrayQueue is empty
public boolean isEmpty(){
	return(this.items == 0);
}

//Determine if the ArrayQueue is full
public boolean isFull(){
	return(this.items == this.capacity);
}


Note that I also added an isFull() method (you will see when this comes in handy)

Now, we arrive at the other operations of the ArrayQueue. Lets consider two algorithms to en- and to dequeue:

enqueue
	if (ArrayQueue == full) 
		throw new FullQueueException
	
	elements[rear] = newEntry
	size++
	rear = (rear+1) % this.capacity;




dequeue
	if (ArrayQueue == empty) 
		throw new EmptyQueueException
	
	temp = elements[front];
	elements[front = null;
	size--
	front = (front+1) % this.capacity;
	return temp


Translating these two algorithms in Java code, results in:
//Enqueue a new item in the array queue
public void enqueue(E newItem) {
	//Check if the ArrayQueue is full
	if(this.isFull())
		throw new FullQueueException("Cannot enqueue, ArrayQueue is full");
	
	//Add the element
	elements[rear] = newItem;
	items++;
	rear = (rear + 1) % capacity;
}

//Dequeue an item from the ArrayQueue
public E dequeue() {
	//Check if the arrayQueue is empty
	if(this.isEmpty())
		throw new EmptyQueueException("Cannot dequeue, ArrayQueue is empty");
	
	E temp = elements[front];
	elements[front] = null;
	items--;
	front = (front+1) % this.capacity;
	return temp;
}


Only one thing remains and that's the front operation. This operation allows an user to peek at the front, but does not dequeue the element. For this program, we return a null value when the Queue is empty (you could also throw the EmptyQueue exception, but that's up to you). This results in:

//Allow the user to "look" at the first element in the queue
public E front(){
	return elements[front];
}


Finslly, add a toString() method to get a string representation of the ArrayQueue. Important to realize is that not only I can have null elements in the array, the array is also circularly defined. This means that I cannot loop form i = 0 till elements.length. I need to loop from the front element till the end of the array and from index i =0 to the rear. This yields in the following toString() method:

//The string representation of the ArrayQueue
public String toString(){
		String temp = "<ArrayQueue[";
		
		for(int i = front; i < capacity; i++)
			if(elements[i] != null)
				temp += elements[i].toString() +",";
		
		if(front == this.rear)
			for(int i = 0; i < this.rear; i++)
				if(elements[i] != null)
					temp += elements[i].toString() +",";
		
		if(temp.charAt(temp.length()-1) == '[')
			return temp + "]>";
		else
			return temp.substring(0, temp.length()-1) + "]>";
	}


Of course, you can customize the formatting of the toString method if you like ;)
Your code for the ArrayQueue should now look like this:

Spoiler


The only thing which remains, is to test if this works. For this purpose, I used the Unit test which was generated when I did this assignment at the University (University of Technology, Delft).

Spoiler


I hope this tutorial was educational for you and I hope you can now make your own ArrayQueue, maybe with some new fancy features ^^

Linked Lists
Level: Intermediate
Assumed knowledge: before you can start this tutorial, you are assumed to have knowledge of:

  • Interfaces
  • Basic Java operations
  • Exceptions
  • Generics
  • Basic knowledge of Object Oriented Programming


Pre-requisite: A self programmed double linked list (DLL) is required. An example can be found here: http://www.dreaminco...topic273905.htm The DLL should be able to support the following operations:

  • Add an element at the rear and remove an element at the front
  • Retrieve the stored element at the front without removing it
  • Support of generics
  • A string representation


Next to the arrayqueue, a double linked list can be used to implement a First in First Out (FIFO) queue. As not everyone read the tutorial about the ArrayQueue, lets recap that part.

Before we start implementing our queue, we need to define what operations it needs to support. Some basic operations of a queue are:

  • size, this returns an integer representing the size of the Queue
  • isEmpty, this returns a boolean to denote if the Queue is empty (or not)
  • enqueue, this is used to enqueue an element to the Queue (add an element to the Queue
  • dequeue, this is used to dequeue an element (remove the first element)
  • front, this returns (but does not remove) the first added element of the Queue


We will also define a custom exceptions for our Double Linked List Queue (DLLQueue), namely:

  • EmptyQueueException, thrown when elements are accessed, while the Queue is empty


So, lets start of with defining our interface:

public interface Queue<E>{
	public int size();
	public boolean isEmpty();
	public void enqueue(E newItem);
	public E dequeue();
	public E front();
}


The next step is to define our exception called the EmptyQueueException. The name says it: when the queue is empty, this exception is thrown. As it is a runtime exception, we need to extend Javas RuntimeException class with our own exception. This results in:

public class EmptyQueueException extends RuntimeException{
	public EmptyQueueException(String err){
		super(err);
	}
}


The main difference between a DLLQueue and an ArrayQueue is the dynamic nature. Because the DLLQueue has a dynamic size, we never have to worry that it gets full Therefore, we do not need a FullQueueException as we had for our ArrayQueue. However, this does come at a price as a DLLQueue will probably use more memory when compared with an ArrayQueue.

Now the interface and the exception are defined, the DLLQueue can be implemented. In order to use our DLLQueue, we need a Double Linked List which supports adding elements at the tail (addLast() operation in DLL tutorial) and removing elements at the head (removeFirst()). Furthermore, the queue should be able to retrieve an element at the front position (getFirst()), without removing it from the DLL.
Next to a variable for the DLL, we also need a variable which represents the size of the DLLQueue. In this context, the size is equal to the amount of elements. So for the DLLQueue we have two variables:

  • elements, variable which denotes the double linked list for the queue
  • size, variable denoting the amount of stored elements in the queue


As everything is defined, we can start to jam some code. Lets start with the constructor. As we are not bounded to a capacity, we can just instantiate an empty DLL for our DLLQueue:

public class DLLQueue<E> implements Queue<E>{
	private DoubleLinkedList<E> elements;	//A variable to store our DLLQueue
	private int size;	//A variable to denote the amount of items in the DLLQueue
	
	//Default constructor, initializes an empty DLL Queue
	public DLLQueue(){
		this.size = 0;
		this.elements = new DoubleLinkedList<E>();	//Instantiate an empty DLL
	}
}


Now add two additional methods, one which returns the size of the DLLQueue and the other which determines whether the DLLQueue is empy. A Queue is empty when no elements are stored in the queue. Thus:

//Method to return the size of the Queue (Amount of stored elements)
public int size(){
	return size;
}

//Method to determine whether the Queue is empty
public boolean isEmpty(){
	return (size == 0);
}


Note that for an ArrayQueue a circular array was used. As a result the front and the rear index has to be tracked, which was because the index has to "wrap around" the size of the Queue when elements are added and removed.
Again, we do not need to implement variables such to keep track of the index of front and rear as the DLL is dynamic. Instead, we can simply add our elements at the tail and remove them from the head. The reason for this approach is caused by the FIFO requirement, the first element in the DLL represents the first inserted element and thus should be removed when it is dequeued. The same holds for the tail: if we look at the tail, this represents the last added element, which is removed the last. Using this knowledge, we can define our remaining methods:

//Method to enqueue an item in the DLLQueue
public void enqueue(E newItem){
	elements.addLast(newItem);
	size++; 	//One element is added
}

//Method to dequeue an item from the DLLQueue
public E dequeue(){
	if(this.isEmpty())	//If the Queue is empty, an EmptyQueueException is thrown
		throw new EmptyQueueException("Cannot dequeue, the queue is empty");
	else{
		size--; //One element is removed
		return elements.removeFirst();
	}
}

//Method to look at the front, without removing it
public E front(){
		if(this.isEmpty())	//If the Queue is empty, an EmptyQueueException is thrown
		throw new EmptyQueueException("Cannot retrieve first element, the queue is empty");
	else
		return elements.getFirst();
}


Finally a string representation can be written. An example would be:

//The string representation of the DLL Queue
//Customizable
public String toString(){
	return "<DLListQueue["+elements.toString()+"]>";
}


In the end, your code for the Queue should look like this:
Spoiler


This tutorial treated the implementation of the Queue by means of a DLLQueue. I hope you enjoyed this tutorial and learned something about Queues and the implementation of it by means of a (Generic) Double Linked List. ^^

References:
Data Structures & Algorithms in Java by Michael T. Goodrich and Roberto Tamassia

Is This A Good Question/Topic? 4
  • +

Replies To: Queues- Arrays and Linked Lists

#2 factordva  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 8
  • Joined: 08-September 12

Posted 28 December 2013 - 03:21 PM

First off, I know this is a late reply, but this post came up right away when I did a Google search for ArrayQueue implementations.
I just started learning data structures in Java myself and found this quite helpful. I would like to add an extra feature to your queue, resizing. I find that this would be a better alternative to simply throwing a FullQueueException when enqueue-ing an item.


Here is the portion of code I am referring to
//Enqueue a new item in the array queue
public void enqueue(E newItem) {
	 //Check if the ArrayQueue is full
	 if(this.isFull())
		 throw new FullQueueException("Cannot enqueue, ArrayQueue is full");
...
}



Resizing can be tricky though since the queue array is circular. This is best explained through example:

Say our array is size 5 and our front and rear are 3,2 respectively:
  0   1   2   3   4
[10][20][40][60][90]


Now, if we were to resize our queue to add another element our desired array would be

  0   1   2   3   4      5
[60][90][10][20][40][newElement] , this way we keep the circular order of elements.


Here is a solution that is actually quite simple, but requires some tricky organization. The idea is to create two variables, one that will loop over a temporary array and another looping over the circular array. We then reassign the new array to reference the old array.

private void resize(int newCapacity){
        int j = front;
        E[] newData = (E[]) new Object[newCapacity]; //create temporary array
        for(int i=0; i<capacity-1; i++){
            newData[i]=elements[j];
            j=(j+1)%capacity;
        }
        //now all is left to do is reassign the queue variables
        front = 0;
        rear = capacity; //important to assign rear before updating for newCapacity
        capacity = newCapacity;
        elements = newData; //elements array reference newData array which has the correct order plus the new capacity
}

And finally, implementing the resize() method
//Enqueue a new item in the array queue
public void enqueue(E newItem) {
	 //Check if the ArrayQueue is full
	 if(this.isFull()) resize(elements.length * 2); //I double the array. Really depends on situation though. 
		 
...
}


Thanks for your post, I know how much effort you put into it and want to thank you for that.

Happy coding, and happy new years!
Was This Post Helpful? 0
  • +
  • -
Page 1 of 1