What will we cover in this tutorial?

We will learn what a Stack is and how to implement it in Python.

But why bother, when you can use a Python list as a Stack? Good question. If you understand how a Stack works, you will know when to use it to efficiently solve problems. The best way to learn something, is by trying to implement it.

Why use a Stack? Check out this tutorial on how to Solve a Maze or Find the Nearest Smallest Element Problem.

Step 1: Understand Stack

A Stack in computer science is like a stack of plates. You can add one on top at the time. Or you can remove the top plate one by one.

A stack can have any number of items on it. In the above illustration you see the following.

1. (left) A stack with 4 elements (1, 2, 3, 4).
2. (mid) A stack of 4 elements where a fifth element is added by a push operation.
3. (right) A stack that had 5 elements, but where the last item (5) is removed by a pop operation.

That is a Stack has two vital operations push and pop. Also, these operations should be done in constant time, O(1). That is they should be done with a performance, which is independent of the size of the stack. Say, if the Stack has 2 elements, then a push (or a pop) takes the same time to execute if the Stack has 2,000,000 elements.

Notice the following with a Stack. The last item you add on the Stack is the first one to get removed. That is Last-in-first-out or LIFO.

Step 2: How to represent a Stack item (Node) in Python code

As always, keep things simple.

How can we represent the above efficiently, such that the operations are not becoming expensive.

We only need to keep track of two things.

1. The item added before. Starting with the first item to be added to point at None.
2. A pointer to the top of the Stack (not in diagram above).

If we have that we can create a Stack. We can make the operations as follows.

• push – Find the top item of the stack using pointer from 2. Then add the new item and let it point at top item. Let stack pointer point at new item.
• pop – Remove top item. Let stack pointer point at item pointed by top item.

Hence, we need a way to represent a item. Such an item is called a Node. This Node should have two things.

1. The element it represents.
2. A pointer to the next node.

This can be turned into Python code like this.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

This class can take the element and next_node pointer as optional arguments as constructed.

Step 3: Creating the stack class to represent the operations push and pop

Let’s start by creating a new class Stack.

class Stack:
    def __init__(self):
        self.stack = None

This creates an empty Stack, where we have the pointer self.stack to point at None.

To add an element can be done by adding a new Node and let it point at the current self.stack.

class Stack:
    def __init__(self):
        self.stack = None

    def push(self, element):
        node = Node(element, self.stack)
        self.stack = node

This works for the initial element push’ed on the Stack and for any element push’ed afterwards.

Now we need to pop the top element of the Stack.

class Stack:
    def __init__(self):
        self.stack = None

    def push(self, element):
        node = Node(element, self.stack)
        self.stack = node

    def pop(self):
        element = self.stack.element
        self.stack = self.stack.next_node
        return element

We need to get the element. Update the self.stack pointer to point to the element below.

Notice, we do not handle the case where the stack is empty, this will cause the pop function to fail. This is handled by adding a a is_empty function, to check whether the Stack is empty.

class Stack:
    def __init__(self):
        self.stack = None

    def push(self, element):
        node = Node(element, self.stack)
        self.stack = node

    def pop(self):
        element = self.stack.element
        self.stack = self.stack.next_node
        return element

    def is_empty(self):
        return self.stack == None

The full code with a print function

Here the full code is provided with a way to represent the Stack as a string. That way you can print it out.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node


class Stack:
    def __init__(self):
        self.stack = None

    def push(self, element):
        node = Node(element, self.stack)
        self.stack = node

    def pop(self):
        element = self.stack.element
        self.stack = self.stack.next_node
        return element

    def is_empty(self):
        return self.stack == None

    def __str__(self):
        if self.stack is None:
            return None
        node = self.stack
        result = "["
        while node is not None:
            result += str(node.element) + " "
            node = node.next_node
        return result[:-1] + "]"


stack = Stack()
for i in range(10):
    stack.push(i)
print(stack)
for _ in range(8):
    stack.pop()
print(stack)

Where the example code in the end will give the following output.

[9 8 7 6 5 4 3 2 1 0]
[1 0]