Stacks and LIFO Structures: Implementation and Use Cases

Few data structures are as ubiquitous as the stack. They are easy to understand and implement but there is power in their simplicity. The purpose of this article is to explain what a stack is and how to implement one, and present three practical use cases. Let’s get started!

Clone the accompanying repository for this article here.

Explanation: Stacks vs Arrays

A Stack is a structure that is responsible for gathering data dynamically following the LIFO principle (last in, first out). As an analogy, you could imagine a stack of cafeteria trays: When you want to add a new tray, it gets introduced to the top of the stack (instead of being inserted somewhere within). Because the last tray is at the top of the stack, it will also be the first to come off when an individual tray is required. Stacks provide two primary functions: ‘pushing’ or introducing a new element, and ‘popping’ or removing the last element.

If we compare this structure to a typical array, some distinct differences become clear. While memory allocation for arrays is taken care of in an intelligent fashion by Swift, in foundational languages array capacity is set during initialization and is static. Stacks on the other hand, allocate and deallocate memory for individual nodes as required, making them very flexible. Additionally, arrays allow access to elements at any index while stacks only interact with the end node. While this might seem limiting (it is…) it actually makes data access very lightweight and fast. Additionally, LIFO behaviour can be very useful for addressing specific situations, which we will look at later in this article.

Stack: Demo Implementation

There are several ways to implement a Stack, but for this demonstration we will create a doubly linked list, which clearly demonstrates dynamic memory allocation as new elements are introduced. To start, let’s look only at the classes and properties required:

First, let’s look at our Node class (lines 1–14). Here, we are using a generic placeholder <> so that the node instance can hold a value of any type that we like. For our purposes, we are limiting the data type to CustomStringConvertible (line 1) so that we can easily print to the console. Then we have two properties which are type Node<T>? (lines 4–5). This is so we can chain our nodes together as needed. The two properties are optional as the first and last nodes will point to nil on their previous and next properties respectively. Because each successive pair of nodes will hold one another, we need to make one of the properties weak to avoid a retain cycle (line 4). Note also that because we are creating a composite type in which one node holds references to other nodes we are required to use a class instead of a struct.

Next, our Stack class (lines 17–23) simply holds the linked list of nodes. We have a rootNode to hold the start of the list, and then an endNode which we use to push and pop nodes at the end of the list. Again, these properties are marked as optional Node<T>? so that they can be nil when the list is empty. A visual representation of our stack with three nodes in it would look like this:

Next let’s take a look at how to push a new element onto our stack. Step 1: Create a new node with the value that we want. Step 2: Provided endNode is pointing to a node, we can assign the next property in our end node to the new node, and the previous property in our new node back to our end node. Remember that the previous property is weak so that we avoid a retain cycle. Step 3: Finally, we can move our endNode pointer to our newNode by accessing its next property. Notice that the memory required for our list grows with the allocation and initialization of the newNode.

Our pop() method removes the end node and returns the value that was in the node. Step 1: We store the value in our end node in a temporary constant val. Step 2: We move the endNode pointer back one element by using its previous property. Step 3: We set endNodes next property to nil. Now, the only reference between the last two nodes is via the previous property which has been marked weak. This means that the node is deallocated from memory. Step 4: We return the value that was in our last node.

With these important methods explained, lets take a look at the final implementation of our Stack class:

The push and pop methods appear exactly as we expect (lines13–32). We can use our push method to create a custom initializer with some variadic values (lines 7–11). Additionally we can check for an empty stack by checking if our rootNode has a value (lines 34–36) and have a basic print method that iterates through our list as long as it is able to access nodes through the next property (lines 38–44).

A basic test of our stack functionality looks like this:

Use Cases for a Stack

Knowing how to implement a stack is one thing, but even more important is recognizing situations for which a stack is well suited. In this next section we will look at three such cases.

Use Case 1: Reversing Order

Because the order of a stack is fixed, reverse order can be achieved very easily by popping elements off one stack and immediately onto another. No messing around with swapping indexes!

Use Case 2: Testing Symmetry

Another good use case for stacks is testing symmetry. In the example below, we are testing a string of brackets to ensure that each closing bracket is the correct counterpart of an earlier opening bracket.

We start by checking that the character count is divisible by two as an odd number of characters would immediately by asymmetrical (line 6). Next, we check that we have valid input by defining a character set of illegal characters and then checking that our input string has a nil range of illegal characters (lines 7–8). To check our closing and opening brackets are a match, we put them into a dictionary as key-value pairs (line 10). In other situations you may be able to calculate the inverse value without having to store pairs in a dictionary. Then we have our stack (line 11). The purpose of our stack in this case is to store opening brackets. As we iterate through our String we can check if our character is an opening bracket by testing if it is a key in our dictionary. If it is, we push it onto our stack. Once we find our first closed bracket, we know that we are working through the second half of our pattern, so we set our firstHalf boolean to false (line 12). If we find any more opening brackets after this point we can check the boolean and indicate a failed test. For each closing bracket, we pop off the last opening bracket and check if they are a correct key-value pair. Once again, we only need to iterate through the string once, so we are getting a lot of value out of a linear algorithm.

Use Case 3: Undoing Commands

Finally, we will use a stack in conjunction with the command pattern, to create an undo history. To start, let’s take a look at a simple bank account object. It has a balance and an overdraft limit and some simple methods for depositing and withdrawing funds:

Instead of calling the deposit and withdraw methods directly, we can store the relevant information in a command. In the snippet below, we specify what kind of action we want to perform with an enum property (deposit or withdrawal) and an amount . We also store a boolean to indicate whether the command was able to be executed (lines 4–11). Notice that if the withdrawal request exceeds the overdraft limit, nothing will happen to the bank account and the succeeded boolean will stay false, otherwise it will become true once the command has completed (lines 18–26). We have two methods for calling or undoing the command, each taking a bank account as an argument (lines 18 & 28). These methods take the bank account and call its instance methods that we saw in the previous snippet.

Going back to the bank account, we can now introduce our commandStack property, which has been initialized with our BankAccountType (line 47). We mark our deposit and withdraw methods as fileprivate so that they can only be accessed by our BankAccountCommand (lines 62 & 66). Now we have two exposed methods: process(command:) and undoLastCommand(). The first accepts a command as an input, executes it with the bank account as the input, and then pushes the command onto the stack. Meanwhile the undoLastCommand method, pops the last command off the stack and performs an undo (lines 51–60).

This is a very simple pattern, and one that is very powerful. The possible applications are endless and make for a satisfying user experience.

And now let’s see the pattern in action:

Wrap Up

In this article, we explored the concept of a stack and LIFO behaviour. We implemented our own stack using a doubly linked list and demonstrated how it allocates and deallocates memory as size of the stack changes. We also looked at three common use cases for stacks: reversing, testing symmetry and undoing. Each of these three situations come up countless times in real world projects. I hope that you will think of a stack as an appropriate structure for handling those needs. As always, thank you for reading!