Stack Data Structure

2020-01-06

• 5 min read

The stack is a collection of items that follows the last-in, first-out concept.

For the addition of new items, the stack only allows it to push the new item to the top. When it comes to removing items, it only allows us to remove the last added item, or commonly known as the top item.

The main API methods are push (add) and pop (remove). But we can also add other methods as part of the API implementation: size, top, and is_empty.

Stack Implementation

We can create a Stack class as a wrapper and use the Python list to store the stack data. This class will have the implementation of the push, pop, size, top, and is_empty methods.

The first step is to create a class definition and how we are gone store our items.

class Stack:
    def __init__(self):
        self.items = []

This is basically what we need for now. Just a class and its constructor. When the instance is created, it will have the items list to store the stack items.

For the push method, we just need to use the list append method to add new items. The new items will be placed in the last index of this items list. So the top item from the stack will always be the last item.

def push(self, item):
    self.items.append(item)

It receives the new item and appends it to the list.

The size method only counts the number of the stack items by using the len function.

def size(self):
    return len(self.items)

The idea of the is_empty method is to verify if the list has or not items in it. If it has, returns False. Otherwise, True. To count the number of items in the stack, we can simply use the size method already implemented.

def is_empty(self):
    return self.size() == 0

The pop method from the list data structure can also be used to pop the item from the stack. It pops the last element as it is expected for the stack. The last added item.

def pop(self):
    return self.items.pop()

But we need to handle the stack emptiness. For an empty list, the pop method raises an exception IndexError: pop from empty list. So we can create an exception class to handle this issue.

class Emptiness(Exception):
    pass

And uses it when the list is empty:

def pop(self):
    if self.is_empty():
        raise Emptiness('The Stack is empty')

    return self.items.pop()

If it is empty, we raise this exception. Otherwise, we can pop the top item from the stack.

We use this same emptiness strategy for the top method:

def top(self):
    if self.is_empty():
        raise Emptiness('The Stack is empty')

    return self.items[-1]

If it has at least one item, we get the top, the last added item in the stack.

Stack usage

The usage would be something like:

stack = Stack()

stack.is_empty() # True

stack.push(1) # [1]
stack.push(2) # [1, 2]
stack.push(3) # [1, 2, 3]
stack.push(4) # [1, 2, 3, 4]
stack.push(5) # [1, 2, 3, 4, 5]

stack.is_empty() # False
stack.top() # 5

stack.pop() # 5
stack.pop() # 4
stack.pop() # 3
stack.pop() # 2

stack.is_empty() # False

stack.pop() # 1

stack.is_empty() # True

We first instantiate a new stack from the Stack class.

Verify emptiness: yes, it is!
Add 5 new items to the stack: [1, 2, 3, 4, 5].
Verify emptiness: not anymore!
Get the top element: 5 because it was the last added item.
Remove 4 items: 5, 4, 3, and 2.
Verify emptiness: empty yet!
Remove the remaining item.
Verify emptiness: it is empty now!

Runtime and Space complexities

Now about space and runtime complexities for each method implemented.

The space is pretty simple. It's a list, so it's O(n) where n is the current number of items in the stack.

The runtime for each method is O(1), constant time.

Reversing a list

We can use the stack data structure for a diverse number of algorithms. An example is to reverse the items from a list.

We want to reverse a list of books, a bookshelf.

def reverse(bookshelf):
    stack = Stack()

    for book in bookshelf:
        stack.push(book)

    reversed_bookshelf = []

    while not stack.is_empty():
        reversed_bookshelf.append(stack.pop())

    return reversed_bookshelf

Create a stack instance
Push each list item to the stack
Create an empty reversed list
Pop each item until the stack is empty
For each popped item, append it to the reversed list
Return the reversed list

The idea is to make the last list item the first to be popped from the stack.

The function usage would be something like:

bookshelf = [
    'Harry Potter',
    'Atomic Habits',
    'Leonardo da Vinci',
    'Sapiens',
    'Peak'
]

reversed_bookshelf = reverse(bookshelf)

print(reversed_bookshelf) # ['Peak', 'Sapiens', 'Leonardo da Vinci', 'Atomic Habits', 'Harry Potter']

Other examples

We can also implement the stack concept in a undo command. Imagine our text editor. For each document change, we store the new document in the stack. If we want to undo the change, we just need to pop the last change and stay with the previous state of the document.

Web Browsers can also use stacks to store the visited website. When the user visits a new website, it pushes the new URL to the stack. When the user goes back, using the "back" button, it pops the last visited website and uses the previous URL.

Resources

My Twitter and Github