Stacks

Well, let’s get right into it with the topic of stacks in more detail. As a recap, a stack is basically just a collection of items where the last item in the collection is the first one to be removed. Kind of like a book stack where the last book on top is the first one to be removed.

Easy enough, right? Well then, let’s dig into an example in coding. 

stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Our initial list of items consists of the numbers 1 up to 10 inclusive. 

Now, if we “pop” from our stack, what do you think will happen? Well, the last item will get removed.

stack.pop()
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9]

And if we we append 10 to the stack again, we’ll get 10 at the end of the list again. Easy enough, right?

stack.append(10)
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Now, we can implement this in two ways. Either with a list that Python already provides or with a linked list that we’ll have to implement ourselves. Since the list one is easier, let’s start off with a list implementation.

stack = []  # We now have an empty stack. To add to it, just append.
stack.append(5)  # We now have 5 in the stack. stack = [5]
stack.append(6)  # We now also have 6 in the stack. stack = [5, 6]
lastItem = stack[-1]  # This is viewing the last item of the stack. In Python, [-1] returns the last element of a list.
stack.pop()  # We have removed 6 from the stack and are now left with just 5 yielding: stack = [5]
stack.pop()  # We have now also removed 5 from the stack so it is now empty.

Now, this is just a super simple implementation of a stack, and Python is doing all the heavy lifting for us. We don’t know anything about what it’s doing under the hood, so let’s try going a bit more in depth and implementing a Stack class ourselves in Python.

Stack Implementation using a List

A stack generally has the pop(), put(), and peek() functions.

Calling the function pop() will return the last element of the stack and “pop” it off the stack.

Calling the function put() will add an element to the end of the stack.

And finally, the function peek() will return the last element’s value without changing anything.

Easy enough, right?

Here’s an example in Python.

class Stack:
    """
    Super simple stack class implemented using a Python list.
    """
    def __init__(self):
        self.stack = []  # Initialize an empty list.

    def length(self):
        return len(self.stack)

    def put(self, value):  # Add an item to a stack.
        self.stack.append(value)

    def peek(self):  # Peek the last element of a stack.
        if self.stack:  # The index -1 in Python returns the last element of a list.
            return self.stack[-1]
        else:
            return None

    def pop(self):  # Pop off the last element of a stack (if exists).
        if self.stack:  # Calling pop() on a Python list will remove the final element and return it.
            return self.stack.pop()
        else:
            return None
        
    def print(self):  # This just gives us a visual representation of how the stack looks. Basically, just a print.
        print(self.stack)

If you know Python, the code should be pretty self explanatory and basic. If not, it’s basically creating a Python class and a constructor that initializes a stack object with an empty list (self.stack) in this case. 

It then contains the functions:

• length() – this returns the length of the stack
• put() – this adds an item to the end of the list
• peek() – this returns the last element of the stack if it contains at least one item
• pop() – this returns and removes the last element of the stack if it contains at least one item
• print() – this just prints out the stack’s elements

Still pretty basic stuff. Now, let’s see it in action.

>>> stack = Stack()  # Initiating a stack.
>>> stack.put(5)  # Add 5 to the stack.
>>> stack.put(10)  # Add 10 to the stack.
>>> stack.put(6)  # Add 6 to the stack.
>>> stack.peek()  # Peek the last element of the stack. The last thing we added is 6, so it returns 6.
6
>>> stack.pop()  # Let's remove or "pop" off the last element.
6
>>> stack.pop()  # Let's remove or "pop" off the last element again.
10
>>> stack.print()  # Let's see how the stack looks. It was [5, 10, 6], but then we removed two items.
[5]  # It is [5] as expected since we removed the last two elements.
>>> stack.length() # Since we removed two elements, we should have 1 element left. 
1
>>> stack.pop()  # Let's pop off the last element.
5
>>> stack.pop()  # Let's try popping again. Oh wait, there's nothing left.
>>> stack.peek()  # There's nothing in the stack, so peeking won't return anything.
>>> stack.length()  # It's an empty stack, so the length is 0.
0
>>> stack.print()  # Again, it's an empty stack, so the print out will print an empty collection.
[]

Well, you might be wondering. This looks super basic. Why would we ever use a stack? Well, the browser that you’re using right now uses a stack to keep track of your history. Let’s try simulating one with our new stack data structure.

>>> stack = Stack()  # Initializing our web browser history stack.
>>> stack.put("www.google.com")  # Let's "visit" www.google.com
>>> stack.put("www.facebook.com")  # Let's now visit www.facebook.com
>>> stack.put("www.zenalc.com")  # Let's now visit www.zenalc.com
>>> stack.put("www.instagram.com") # Let's now visit www.instagram.com
>>> stack.put("www.amazon.com") # Let's now visit www.amazon.com
>>> stack.pop()  # We now "press" the back button, and pop www.amazon.com from our stack and go to Instagram.
'www.amazon.com'
>>> stack.peek()  # We are now on Instagram.
'www.instagram.com'
>>> stack.pop() # Let's get out of Instagram.
'www.instagram.com'
>>> stack.pop()  # Now let's get out of this blog.
'www.zenalc.com'
>>> stack.put("www.uber.com")  # Now let's enter Uber.
>>> stack.pop()  # Let's get rid of Uber.
'www.uber.com'
>>> stack.pop()  # Remember, once we exited ZENALC, we were on Facebook. But then we entered and then exited Uber. So, we now exit from Facebook.
'www.facebook.com'
>>> stack.pop()  # Now, we get out of Google as Google came before Facebook.
'www.google.com'
>>> stack.pop()  # The stack is now empty meaning the "back" button must be greyed out.

Not too shabby, huh? Also, think about a text processor like Microsoft Word. How do you think the program knows how to “undo” something? If you said using a stack, give yourself a pat.

There are many other useful applications of stacks as well. Most commonly they’re used for stuff like reversing something or traversing deep into something like a tree or graph (more on this later when we discuss DFS). 

Well, that was pretty easy, right? Let’s move on to implementing this using a linked list. (PS, if you don’t know what a linked list is, you might want to stop here and look up what a linked list is.)

Stack Implementation using a Linked List

As a brief recap, a linked list is a collection of nodes that contain a value and have a pointer to another node. Here’s an example.

Say, we have our first node: Node with an value of 5 with it pointing to nothing. 

It is then represented like this: [5] -> Nothing

Now, let’s create another Node with a value of 10. Then let’s have our first node point to this node.

It now looks like: [5] -> [10]

They are kind of similar to an array in that they also hold data, but the way they insert, delete, and access that data is fundamentally different. 

Let’s try implementing one. We’ll get a better idea once we create it.

class StackLinkedList:
    """
    Implementation of a stack using a linked list.
    """

    def __init__(self):  # Initialize it setting head node to be equal to None and length to 0.
        self.head = None  # Our initial head node doesn't exist as the stack is empty.
        self.length = 0  # The length of our stack is also empty initially.

    def put(self, val):  # Function to add to the stack.
        if self.head is None:  # If the head of the stack (meaning the end) is empty, we set the head equal to the node.
            self.head = Node(val)  # Set it equal to a node with a value of the one passed in.
            self.length = 1  # It's our first node, so set the length to 1.
        else:
            node = Node(val)  # If the stack already has a node, we create a new node.
            node.next = self.head  # We set the next pointer of this node to our current head.
            self.head = node  # Now, we point our head of this stack to the new node we just made.
            self.length += 1  # Increment the length by 1.

    def peek(self):  # Function to peek the stack.
        if self.head is not None:  # If the stack is not empty, return the head's value.
            return self.head.value
        else:
            return None

    def size(self):  # Return the size of the stack.
        return self.length

    def pop(self):  # Remove an element from the stack.
        if self.head is not None:  # Make sure the head isn't already empty.
            self.length -= 1
            temp = self.head.value  # We need to return the value of this node, so we set it to a temporary variable.
            self.head = self.head.next  # Since, we popped the stack, the pointer of the head changes to the head node's next reference.
            return temp  # Return whatever we just popped off.

    def print(self):  # Print out the stack.
        print('[', end="")
        node = self.head
        while node is not None:
            if node.next is not None:
                print(node.value, end=", ")
            else:
                print(node.value, end="")
            node = node.next
        print("]")

Pretty much the same functions as the one from our initial implementation using a list. 

However, look at the way the pop() and put() functions are implemented. The function pop() just checks if the head of the linked list exists or not. If it does, then it sets the pointer of the head to the head’s next value. If it doesn’t, it doesn’t do anything as that means the stack is empty. 

The function put() also works differently. It checks if the head is empty or not. If it is empty, it sets the head of the stack equal to the new node and sets the length of the stack equal to 1. If it isn’t empty, it creates a new node, then it sets that new node’s next pointer to the head and increments the length by 1. It then reassigns the head to the new node (remember, this is a stack; so, the last element will be the head).

Playing around with this new stack:

>>> stack = StackLinkedList()  # Initiate our stack.
>>> stack.put(5)  # Add 5 to the stack.
>>> stack.put(500)  # Add 500 to the stack.
>>> stack.put(50000)  # Add 50000 to the stack.
>>> stack.put(1231) # Add 1231 to the stack.
>>> stack.put(12312231) # Add 12312231 to the stack.
>>> stack.put(-501) # Add -501 to the stack.
>>> stack.put(52) # Add 52 to the stack.
>>> stack.print()  # Notice how the visual representation looks different in our implementation. 
[52, -501, 12312231, 1231, 50000, 500, 5]  # The last element to be added is the one first one in the list.
>>> stack.peek()  # Peeking shows us the first item to be removed, which is 52 in this case.
52
>>> stack.pop()  # Let's pop it out.
52
>>> stack.peek()  # Now, -501 is the last element.
-501
>>> stack.size()  # Our size of the stack is now 6.
6
>>> stack.print()  # Let's print it again.
[-501, 12312231, 1231, 50000, 500, 5]  # We removed 52, so this is expected.
>>> stack.pop()  # Let's remove -501.
-501
>>> stack.pop()  # Let's remove 12312231.
12312231
>>> stack.pop()  # Let's remove 1231.
1231
>>> stack.size()  # We removed 3 items, so our size is 3 as expected.
3
>>> stack.put(50)  # Let's add 50.
>>> stack.size()  # Size is now 4.
4
>>> stack.print()  # The 50 we just added is the first item ready to be "popped" off.
[50, 50000, 500, 5]