Implementing a Queue in Java

Let’s begin implementing a queue in Java. Our queue implementation will be fairly similar to our stack implementation with some key differences. It will be implemented internally like a linked-list. Implementing it in this way will allow for us to achieve good performance (constant time) when add/removing items from the queue.

Declare our Queue class:

public class MyQueue<T> {

}

Like our Stack class our Queue class is declared to have a type of T. This means that a new MyQueue class is instantiated to hold objects of a chosen data type.

Declare a node class. This can be the same node class we used in our Stack implementation:

private class Node<U> {
	public U data;
	public Node<U> next;
	public Node(U data) {
		this.data = data;
		next = null;
	}
}

Our node class needs to hold a pointer to the next node in the queue as well as the data contained in the node.

Next we’ll declare the class level variables. We’ll need a variables to hold the head node of the queue, the last node of the queue, as well as the size of the queue.

private Node<T> head;
private Node<T> last;
private int size;

Declare a constructor for our MyQueue class. It needs to initialize the head and tail variables to null. It also needs to initialize the size variable to be 0.

public MyQueue() {
	head = null;
	last = null;
	size = 0;
}

We need a function to add items to our queue. This will need to add items to the back of our queue (AKA the end of our internal linked list). During this step we need to make sure that all three of our class-level variables are updated appropriately.

The function has two use cases to cover:

1. An empty list (the head and last nodes are null)
2. A non-empty list (the head and last nodes are not null)

Here’s how we will handle each case:

1. Declare a new node and set both the head node and last node to the declared node.
2. Declare a new node. Set the next node of the last node to be the newly declared node. Then set the last node to be the newly declared node.

Declare our add function. It needs to input the data to be added as a parameter.

public void add(T data) {

}

Declare our node to be added to the queue. Also increment our size by one at the end of the function.

	Node<T> newNode = new Node<T>(data);
	// put code to add the declared node to our queue here
	size++;

Add an if statement to check if the queue is currently empty. If the queue is empty we need to handle it differently then if the queue has items.

	if(head == null) {
		// add the item to our empty queue here
	} else {
		// add the item to our non-empty queue here
	}

If the queue is empty we simply set the head and last nodes to the newly declared node.

		head = newNode;
		last = newNode;

If the queue is non empty we add it to the end of the queue. We do this by first setting the next node of the last node to the newly declared node. We then set the last node to be the newly declared node (as it is now the last node in the queue).

		last.next = newNode;
		last = newNode;

The finished add function looks as follows:

public void add(T data) {
	Node<T> newNode = new Node<T>(data);
	if(head == null) {
		head = newNode;
		last = newNode;
	} else {
		last.next = newNode;
		last = newNode;
	}
	size++;
}

Next let’s add a peek function. This function will return whatever item is at the beginning of our queue.

The function has two use cases to cover:

1. An empty list (the head and last nodes are null)
2. A non-empty list (the head and last nodes are not null)

Here’s how we will handle each case:

1. Return null.
2. Return the data contained within the head node (the head node contains the data of the first item in the queue).

Here’s what the function definition looks like:

public T peek() {

}

The implementation of this is fairly simple. If the head node is equal to null we return null. If it is not equal to null we return the data contained in the head node.

	if(head == null)
		return null;
	return head.data;

The completed function as is follows:

public T peek() {
	if(head == null)
		return null;
	return head.data;
}

We will finish implementing our queue in the Implementing a Queue in Java - Part Two.

Data Structures