Data Structures ## 3 Steps to Understand and Implement a Stack in Python

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.

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

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.

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
```

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]
```

Data Science for beginners in this free online course Data Science is over complicated by…

2 months ago

15 Machine Learning Projects That Will Teach You All You Need as Machine Learning Authority…

2 months ago

Why learn Python? There are many reasons to learn Python, and that is the power…

2 months ago

What will you learn? How to use the modulo operator to check if a number…

2 months ago

There are a lot of Myths out there There are lot of Myths about being…

4 months ago

To be honest, I am not really a great programmer - that is not what…

4 months ago