## 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.

*(left)*A stack with 4 elements (1, 2, 3, 4).*(mid)*A stack of 4 elements where a fifth element is added by a**push**operation.*(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.

- The item added before. Starting with the first item to be added to point at None.
- 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.

- The element it represents.
- 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]