Home › Java › A Queue Class in Java

A Queue Class in Java

Posted on Posted in Java Tagged with , , , ,

What is a Queue?

In English, a queue is a waiting line. In Computer Science, a queue is a collection where elements are added on one end (the rear) but removed from the other end (the front).

Queue elements are processed in a first in, first out (FIFO) manner; they are removed in the same order as they are added to the queue. This is in contrast with stacks where elements are processed in a last in, first out (LIFO) manner.

Queues have many applications in software systems. One example is implementing input/output buffers using queues. An I/O buffer is a storage space temporarily holding data, and it serves between the program and the physical storage. Another example is message queues, which are used for data communications between senders and receivers. This is often used for asynchronous communications, where the sender and the receiver do not need to interact with the queue at the same time.

Design a Queue Class

A queue allows two operations accessing its elements:

  • Dequeue: removes one element from the front
  • Enqueue: adds one element to the rear

We can build queues using arrays. However, if we fix the front of a queue at index 0 of the array, we need to shift elements for each dequeue operation. To avoid shifting, we can use circular arrays, where elements are order in a cycle.

In particular, for our Queue class, we use three attributes together with an array:

  • count: the number of elements
  • front: the index of the first element
  • rear: the index of the next to the last element

The fields and methods of the Queue class are as below:

  • T[] data: the array storage
  • int count: the number of elements
  • int front: the index of the first element
  • int rear: the index of the next slot
  • void enqueue(T e): adds one element
  • T dequeue(): removes one element
  • int size(): returns the number of elements

Implement the Queue Class

The following is an implementation of the Queue class in Java.

import java.util.Arrays;
public class Queue <T>
{
	private T[]		data;
	private int		count;
	private int		front;
	private int		rear;

	public Queue()
	{
		queue = (T[]) new Object[10];
		count = front = rear = 0;
	}
	void expandCapacity()
	{
		T[] newData = (T[]) new Object[data.length * 2];

		// copy elements to the new array one by one
		for (int index = 0; index < count; index++)
			newData[index] = data[(front + index) % data.length];

		front = 0;
		rear = count;
		data = newData;
	}	
	void enqueue(T e)
	{
		if (count == data.length)
			expandCapacity();
		data[rear] = e;
		rear = (rear + 1) % data.length; // may round up
		count++;
	}
	T dequeue() throws Exception
	{
		if (count <= 0)
		{
			throw new Exception("Queue empty"); 
		}
		count--;
		T ret = data[front];
		data[front] = null;	// set the removed element to null
		front = (front + 1) % data.length;
		return ret;
	}	
	boolean isEmpty()
	{
		return count == 0;
	}
	int size()
	{
		return count;
	}
	public String toString()
	{
		return "size: " + count + ", front: " + front + 
               ", rear: " + rear + ", " + Arrays.toString(queue);
	}
	
	public static void main(String[] args) throws Exception
	{
		Queue<String> q = new Queue<String>();
		q.enqueue("A");
		q.enqueue("B");
		q.enqueue("C");
		q.enqueue("D");
		System.out.println(q);
		
		while (! q.isEmpty())
			System.out.println(q.dequeue());
		
		Queue<Integer> q2 = new Queue<Integer>();
		for (int i = 10; i < 100; i += 10)
			q2.enqueue(i);
		
		while (! q2.isEmpty())
			System.out.println(q2.dequeue());
	}
}

Related Posts

Comments

comments