Data Structures

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

Rune

Share
Rune

## The Best Free Data Science Course Online

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

2 months ago

## The Ultimate 15 Machine Learning Projects With Source Code

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

2 months ago

## Learn Python FREE Online

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

2 months ago

## How to Check if a Number is Even or Odd with Python

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

2 months ago

## The Truth About Being a Python Software Contractor

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

4 months ago

## Do This and 10X Your Salary as a Software Engineer

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

4 months ago