Now we’re really starting to get into the thick of it! We’re up to our fourth data structure which in this case is the queue. By the time we’re finished here, we’ll have a pretty solid understanding of all the list style structures (of course, until we hit hash tables). Let’s get to it!
Table of Contents
What is a Queue?
Like the name suggests, queues are like the lines at a super market. Each customer is served in the order in which they are lined up. For a queue, that means data flows from the back of the list to the front of the list where it is eventually processed. In computer science, these ends are called the head and the tail.
Like stacks, queues are another special case list structure. However, in a queue, both ends of the list are used. In this data structure, elements are always inserted at the tail and removed at the head. This restriction enforces first-in first-out (FIFO) behavior.
The main operations for a queue are enqueue and dequeue. As we can imagine, these operations directly correlate to insert and delete. The enqueue operation places a new element in a node at the tail end of the list. This object will slowly make its way to the front until it is dequeued at the head of the list. Together, these two functionalities are all we need to create a queue.
Properties of Queues
Just like stacks, queues are just special case linked lists though they can be implemented using arrays. We keep the same exact structure as a linked list but we only expose the outermost nodes: the head and the tail. This allows us to maintain a very important property: FIFO. If we ever need to preserve the order of data as it comes in, we’ll use a queue.
However, not all queues are created equal. As well see below, some queues enforce a sorting order that is not related to insertion order. In these cases, we’ll have what’s called a priority queue.
Applications of Queues
Queues are typically used when serving requests for a single shared resource like a CPU or a device like a printer. In these scenarios, we care that requests are processed in the order in which they are received. In the case of the CPU, instructions need to make there way down the pipeline in the same order as the source code. For printers, print jobs need to be completed on a first-come-first-serve basis.
Queues can also be used to handle asynchronous data transfer. In other words, queues make great data structures in threading situations. If one thread needs to contact another, we can define a queue between them that stores messages. The first thread can simply store messages in this queue and hope that the second thread is properly monitoring the other end.
That said, there are more complex queue structures which allow manipulation of the contents. For example, queues can be modified to support object priority. This priority determines where exactly the new object will go when placed in the queue. Objects of the same priority are sorted by insertion order like a normal queue. Typically, priority queues are used for applications like bandwidth management. However, priority queues are also used as the core of many important algorithms like Huffman Coding and Dijkstra’s Algorithm.
Java Queue Syntax
While Java has support for Queues
in its collections library, we’re going to go ahead and implement one by hand. We’ll continue to use the integer implementation of node until we get a better understanding of generic typing.
Class Definition
The basic queue class supports two main functions: enqueue and dequeue. As you can imagine, these functions are the equivalent to insert and delete. As a result, the code needed to create a queue looks more like the following:
public class Queue {
private Node head;
private Node tail;
public Queue() {
head = null;
tail = null;
}
}
We simply define both ends of the queue as nodes in a linked list (though could have just as easily used an array).
Insertion
Using the queue structure above, insertion just requires us to implement the enqueue method.
public void enqueue(int element) {
Node toAdd = new Node(element, null);
if (tail != null) {
this.tail = this.tail.setNext(toAdd);
} else {
this.tail = toAdd;
this.head = toAdd;
}
}
Here we simply check if the queue is empty. If it is, we set both the head and the tail to the new node. Otherwise, we set the new node as the tail of the list.
Deletion
Deletion just requires that we implement the dequeue functionality. Here, we have to make sure the function returns our integer.
public int dequeue() {
Node toRemove = this.head;
if (this.head == null) {
throw new NoSuchElementException();
} else if (this.head.getNext() == null) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.getNext();
}
return toRemove.getPayload();
}
For deletion, we end up with three cases: an empty list, a single element list, and a multiple element list.
Summary
Overall, queues are just like stacks and linked lists, so naturally their performance is largely the same.
| Algorithm | Running Time |
|---|---|
| Access | O(N) |
| Insert | O(1) |
| Delete | O(1) |
| Search | O(N) |
Recent Posts
As the semester starts to wrap up, I'm a bit busy and a bit burnt out. As a result, I thought I'd have a little fun writing about nasty little bugs I've run into over time. I'll keep it short; don't...
I find the structure of relational databases to be appealing. They allow you to store data in various tables that eliminate redundancy, reduce storage size, and combine easily. Therefore, it should...