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]
Python for Finance: Unlock Financial Freedom and Build Your Dream Life
Discover the key to financial freedom and secure your dream life with Python for Finance!
Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.
Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.
Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.
Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!
Python for Finance a 21 hours course that teaches investing with Python.
Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.
“Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.
