Data Structure — Queue (Java)
Data Structures
Java Implementation - Queue
# A complete working Java program of a Queue in 40 lines of code.
Step 1 — Node class
Implementing a Queue is reasonably straightforward. We just need a class called Node, that stores a next and data value. To make our lives easier we add in a constructor and set the value. The name Item is a type parameter, a symbolic placeholder for some concrete type to be used by client.
private static class Node<Item>{
private Item data;
private Node<Item> next; public Node(Item data){
this.data = data;
}
}
Step 2 — Create Head and Tail Nodes
The following code goes within the Queue class, underneath the Node class. For our Queue implementation we need to create a Node object called head and Node object called tail. We then remove an object from the head(represents the front of the queue) and add an object at the tail(represents the back of the queue).
private Node<Item> head;
private Node<Item> tail;Step 3 — isEmpty & Peek Methods
The isEmpty()method is very simple, just return if the head value is null;head == null . If the head value is null, then the queue is empty, otherwise it is not.
public boolean isEmpty(){
return head == null;
}The peek()method will return head.data. This will throw an exception when head is null. If you want you can go explicitly check for that exception.
public int peek(){
return head.data;
}Step 4 — Add & Remove Node
To add a node(enqueue) to the tail of the Queue, first you must create the node. Then if the tail is not null, let tail’s next pointer point to the new node, and then update the tail. Then we want to make sure that, even in the case when the Queue is completely empty(in which case head == null) then this value should be the head value.
public void enqueue(Item data){
Node<Item> node = new Node<Item>(data);
if (tail != null){
tail.next = node;
}
tail = node;
if(head == null){
head = node;
}
}To remove a node(dequeue) from head of the Queue. First thing is to get the head datadata = head.data. Then we simply want to change the head value to be the next value. So set head = head.next and this basically removes it from the Queue. Then we say, if the head value is null, make sure to set the tail value to null too. Then return that data.
public <Item> dequeue(){
Item data = head.data;
head = head.next;
if(head == null){
tail = null;
}
return data;
}Full Implementation
This is what your code should look like :)
Test Cases
It is good practice to test your good, to see if it works (:
Congratulations on completing the Java implementation of a Queue. So that is the basics of implementing a Queue. The methods follows pretty logically from the actual design and the algorithm behind it. :) !
Dictionary
Abstract Data Types(ADTs) — This is a data type who’s representation is hidden from the client. We associate data with the function implementations and we hide the representation of the data from the client. When using an ADT, we focus on the operations of the API and pay no attention to the data representation; when implementing an ADT, we focus on the data, then implement the operations.
Generics — Also known as parameterised types, is an essential characteristic of collection Abstract Data Types(ADTs) is that we should be able to use the for any type of data. Our use of them in the above context involves a small bit of extra Java syntax and is easy to understand. The notation <Item> after the class name in the above implementation, defines the name Item as a type parameter(a symbolic place-holder for some concrete type to be used by the client). You can read Queue<Item> as “Queue of Items”.
Disclaimer: When implementing this Queue, we do not know the concrete type of Item, but a client can use our Queue for any type of data, including one defined long after we developed our implementation. The client code provides a concrete type when the Queue is created: we can replace Item with the name of any reference data type(consistently, everywhere it appears). This provides exactly the capability that we need.
