The Queue data structure is very useful in algorithms. It’s very used when traversing graphs for example. It’s also very efficient in terms of performance to insert and remove the first or last elements.
What is Queue?
We can use an analogy of a real-world queue to explain what is a queue in computer science. Let’s imagine a person that goes to a bank queue to pay a bill. The first person to arrive in the queue is the first person out or the first person to be served. The last person arriving in the queue will be the last one to be served.
Let’s see the diagram:
In Java, we already have an implementation of the data structure queue. It’s the interface Queue. Let’s see in practice the same example we’ve seen in the diagram above:
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> peopleQueue = new LinkedList<>();
peopleQueue.add("Wolverine"); // First in & first out
peopleQueue.add("Juggernaut");
peopleQueue.add("Xavier");
peopleQueue.add("Beast"); // Last in & last out
var queueSize = peopleQueue.size();
for (int i = 0; i < queueSize; i++) {
System.out.print(peopleQueue.poll() + " ");
}
}
}
Output:
Wolverine Juggernaut Xavier Beast
Notice in the code above that we are inserting data only at the beginning of the queue. Then we use the poll method to remove and return the inserted elements.
There is an important detail when using the implementation of LinkedList. If we look into the internal implementation from LinkedList, notice that the data is stored in the data structure of a graph:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// Omitted other code
}
Since LinkedList uses the structure of a graph we have great performance when inserting or removing elements at the beginning or the end of the List. However, it’s slow to search for a specific element since the whole list has to be traversed object by object. Notice also that LinkedList can’t be accessed via an index like an array which is much faster, it’s an O(1) time complexity.
Inserting Elements at the Start and the End of the Queue
To add elements at the end of the queue there is a ready-to-use interface in Java called Deque. Deque is the short name for a double-ended queue that enables us to insert and remove elements from the start and the end of the queue.
Let’s see how we can use Deque to add an element at the first and last position of the queue:
public class DequeAddFirstAndLast {
public static void main(String[] args) {
Deque<String> xmenQueue = new LinkedList<>();
xmenQueue.add("Wolverine");
xmenQueue.addFirst("Cyclops");
xmenQueue.addLast("Xavier");
showAndRemoveQueueElements(xmenQueue);
}
private static void showAndRemoveQueueElements(Deque<String> peopleQueue) {
var queueSize = peopleQueue.size();
for (int i = 0; i < queueSize; i++) {
System.out.print(peopleQueue.poll() + " ");
}
}
}
Output:
Cyclops Wolverine Xavier
Deleting Elements at the Start and End of the Queue
In the following code, we will add three elements to the queue and then will use removeFirst method to remove the first element “Wolverine” and the last element “Xavier”. Lastly, we will show and remove the remaining element “Cyclops”:
import java.util.Deque;
import java.util.LinkedList;
public class DequeDeleteFirstAndLast {
public static void main(String[] args) {
Deque<String> xmenQueue = new LinkedList<>();
xmenQueue.add("Wolverine");
xmenQueue.add("Cyclops");
xmenQueue.add("Xavier");
System.out.println("Removing first: " + xmenQueue.removeFirst());
System.out.println("Removing last: " + xmenQueue.removeLast());
showAndRemoveQueueElements(xmenQueue);
}
private static void showAndRemoveQueueElements(Deque<String> peopleQueue) {
var queueSize = peopleQueue.size();
for (int i = 0; i < queueSize; i++) {
System.out.print(peopleQueue.poll() + " ");
}
}
}
Output:
Removing first: Wolverine
Removing last: Xavier
Cyclops
Big(O) Notation – Time Complexity of a Queue
Insert an element at the beginning of the queue
To insert an element at the beginning of the queue we only link a new object into the first element of the LinkedList. Therefore, the complexity is O(1). Take a look at the following code:
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
Insert an element at the end of the queue
This is only possible to accomplish with a double-ended queue. The time complexity is O(1), the same as inserting an element at the beginning of the queue. Also, the code is very similar as you can see in the following code:
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Insert or delete an element in the middle of the queue
The time complexity is O(n) because it’s necessary to traverse the graph of objects until we can add an element in the wished position.
Find an element
The time complexity is O(n) and that’s because until the element is found it’s necessary to traverse the graph, element by element.
Delete the first element of the queue
Similarly to the insertion, the time complexity is O(1) because we have direct access to the first element.
To explain the following code, we pass the first element as a parameter, then we assign the data to new variables. Then we assign null from the next element to help the garbage collector collect the dead instance. In the first element instance variable we put the reference of the next element:
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
Delete the last element of the queue
It’s only possible to delete the last element by using a double-linked list. Also, since a double-linked list stores the last element into a separate variable, we have direct access to it to perform the deletion. Therefore, the time complexity is O(1).
To briefly explain the following code, we receive the last element by parameter, variable “l”. Then we pass the previous element attached to the last element to a new variable. We pass null to item and prev from the last element to help the garbage collector collect those dead instances. Finally, we pass the reference from prev to the last element instance variable.
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
Summary
The queue data structure is a very important data structure to be mastered and it’s used in the famous breadth-first search algorithm.
Let’s see the key points from the queue data structure:
- It uses the FIFO (First-in First-out) structure. The same from a real-world queue.
- To insert and delete at the beginning or at the end of the queue the time complexity is O(1).
- To find an element in a queue with a LinkedList the time complexity is O(n) because it’s necessary to traverse all elements for the worst-case scenario.
- To delete or insert an element in the middle of the queue the time complexity is also O(n).
