Data Structures – Page 9 – The Renegade Coder

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! 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. AlgorithmRunning TimeAccessO(N)InsertO(1)DeleteO(1)SearchO(N)