Implementing a Queue in Java - Part 2

Let’s get back to implementing our MyQueue class! Our queue class needs a function to remove items from the queue. This function needs to remove the first item in our queue, decrement our size variable, and return the removed item.

The function has three use cases to cover:

1. An empty list (the head and last nodes are null)
2. A non-empty list of size > 1 (the head and last nodes are not null, as well as head is not equal to last)
3. A non-empty list of size 1 (the head and last nodes are not null, as well as head is equal to last)

Here’s how we will handle each case:

1. Return null.
2. Get our result from the head node. Set the head node to the next node. Decrement the size variable. Return the result.
3. Get our result from the head node. Set the head node to the next node (which is null). Set the last node to null. Decrement the size variable. Return the result.

Declare our pop function. It needs to return the data that is removed.

public T pop() {
	
}

If the list is empty (AKA the head node is equal to null) simply return null.

	if(head == null)
		return null;

Get the result from our head node and set our head node to the next node.

	T result = head.data;
	head = head.next;

If our head node is now equal to null then our queue is now empty. If our queue is empty then we also need to set the last node equal to null.

	if(head == null)
		last = null;

Finally we decrement our size variable and return the item that we have removed.

	size--;
	return result;

The finished pop function looks as follows:

public T pop() {
	if(head == null)
		return null;
	T result = head.data;
	head = head.next;
	if(head == null)
		last = null;
	size--;
	return result;
}

Let’s add a function to return the size of the queue. It simply needs to return the size variable. It looks as follows:

public int getSize() {
	return size;
}

Add a function to clear the queue. If the queue is non-empty it needs to set the head and last variables to null as well as the size to zero. The function definition is as follows:

public void clear() {

}

If the head is not equal to null (AKA the queue is not empty) then set the head and last to null and the size to 0.

	if(head != null) {
		head = null;
		last = null;
		size = 0;
	}

The finished function is as follows:

public void clear() {
	if(head != null) {
		head = null;
		last = null;
		size = 0;
	}
}

Let’s add a function to return the contents of the queue as a string. The function is defined as follows.

public String toString() {

}

Declare a StringBuilder s, add the characters “[" and "]” to it, and return the string version of it. In between the “[" and "]” characters we will put the data in the queue.

	StringBuilder s = new StringBuilder();
	s.append("[");
	// add the data in the queue to the StringBuilder s here
	s.append("]");
	return s.toString();

If the queue is non-empty then we will loop through all the items in our internal linked-list and add them to the StringBuilder s. As long as the item isn’t the last item in the queue then we will add a comma and a space between the items as a separator to the StringBuilder. We loop through the list by setting the Node n to the first item in the queue (head). While this n is not equal to null we set it to the next node in the list. When n eventually becomes equal to null we have looped through the entire list.

	if(head != null) {
		Node<T> n = head;
		while(n != null) {
			s.append(n.data);
			if(n.next != null)
				s.append(", ");
			n = n.next;
		}
	}

The finished function looks as follows:

public String toString() {
	StringBuilder s = new StringBuilder();
	s.append("[");
	if(head != null) {
		Node<T> n = head;
		while(n != null) {
			s.append(n.data);
			if(n.next != null)
				s.append(", ");
			n = n.next;
		}
	}
	s.append("]");
	return s.toString();
}

The finished MyQueue class looks as follows:

public class MyQueue<T> {
	private class Node<U> {
		public U data;
		public Node<U> next;
		public Node(U data) {
			this.data = data;
			next = null;
		}
	}
	private Node<T> head;
	private Node<T> last;
	private int size;
	public MyQueue() {
		head = null;
		last = null;
		size = 0;
	}
	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++;
	}
	public T pop() {
		if(head == null)
			return null;
		T result = head.data;
		head = head.next;
		if(head == null)
			last = null;
		size--;
		return result;
	}
	public T peek() {
		if(head == null)
			return null;
		return head.data;
	}
	public int getSize() {
		return size;
	}
	public void clear() {
		if(head != null) {
			head = null;
			last = null;
			size = 0;
		}
	}
	public String toString() {
		StringBuilder s = new StringBuilder();
		s.append("[");
		if(head != null) {
			Node<T> n = head;
			while(n != null) {
				s.append(n.data);
				if(n.next != null)
					s.append(", ");
				n = n.next;
			}
		}
		s.append("]");
		return s.toString();
	}
}

Data Structures