Stack and Queues!
Stacks and queue. Snacks and glues. Smacks and chews. What are these mysterious words? They are data structures! This week, in my ongoing attempt to decipher the arcane mysteries of data and how it’s structured, we’re going to be taking a quick to moderately lengthy look at what exactly a stack and a queue is, and what they’re used for.
The first thing to know about these data structures is that they’re essentially more complex versions of a data structure we’ve already talked about. The indomitable linked list. What makes stacks and queues different from their more prototypical parent, is the manner in which nodes are added and removed from the linked lists which comprise them. As you remember linked lists are sets of nodes, which are in themselves, simple data structures which contain two attributes, some small piece of data, and a pointer to link them to the next link in the list. A standard linked list can have nodes removed from the head, the tail, the very middle, any which way, as long as the nodes adjacent to the removed or added node are updated to account for their new neighbors. Stacks and queues on the other hand must follow very specific rules.
Let’s start with a queue. Nodes in a queue can only be added to tail of a list. If a node is ever to be removed from the list, it must come off the head. This variety of ingress and egress is commonly referred to as “first in-first out”, or FIFO for short. In this way, data structure queues are very similar to real world examples of a queue. This type of data structure is very helpful when you are modeling environments where sequence of entry is very important. For example, if you are building a web app that instantiates a new pre-order ticket for some product that will be released with a very limited supply, it is very important that sequence be maintained when saving data. Queues are indispensable in that sort of situation.
In practical terms of how to execute a queued linked list, it is necessary to create custom functions for your queue class. It’s not sufficient to have a bunch of methods like add to head or add to tail. Two methods need to be built, namely a dequeue and enqueue method to remove and add nodes from the list, respectively. This ensures that the linked list functions properly as a queue.
The second flavor of linked list to discuss is the stack. Not only is the stack easier to spell, it’s also every so slightly easier to understand. Imagine a stack of cats.
Cats are famously temperamental. If one were to try and remove a cat from somewhere in the middle of this stack, the delicate balance of politics and trust would be upset, sending the entire stack into a bloodthirsty rage. It is incredibly important that stack data structures, exactly like actual stacks of cats, must be handled in a very specific fashion. Namely, only take off the top, and when adding to the stack, only place new additions on the top. This system is known as a “first in-last out” system. Stack data structures can be used to store data such as one browser history. Recently visited pages are added to the top of the stack, and as you navigate backwards through your history, are removed from the top of the stack.
In order to make a functioning stack data structure, the class in question must have a method that is able to locate the last added node, and remove only that one, in case such an action should be required.
Those are the data structures for this week! Swing by next week, when I take a deep dive out of the world of linear data structures, and into the mystifying murk of whatever a hash map is.
