0
0
A stack is a data structure in computer science that stores a collection of items in a last-in-first-out (LIFO) order. This means that the item that was added last to the stack is the first one to be removed from it.
The main operations that are performed on this data structure include
- A .push() function that adds an item to the top of the stack.
- B .pop() function that removes and returns the item that was at the top of the stack.
This type of collection is similar to a stack of objects such as books, where the topmost book has to be taken off to access the ones below. Stacks are useful for implementing actions such as a depth-first search.
In this write-up, we will explain how to create and implement stack in Python. So, let’s start this interactive tutorial.
Plan for Stack Implementation in Python
To implement a stack in Python, we need to figure out what features we want our stack to have. The basic operations of a stack are .push() and .pop(), which add and remove items from the top of the stack. But we might also want some additional features, such as:
- The ability to use Python’s len() function to check how many items are in the stack, and to alert us when the stack is empty. This is a good practice to avoid errors when using a stack in a program.
- A .peek() function to show us the value of the top item on the stack without taking it off.
- The ability to handle the situation when we try to use .peek() or .pop() on an empty stack. We could return a special value like NaN, but that might cause problems later, especially if we add a NaN value to the stack. A better option is to raise an exception when we attempt to use these functions on an empty stack. This way, we can catch such errors during testing and update the code that uses the stack accordingly.
Steps to Building Stack Class
As there is no shortage of Python libraries for beginners, it becomes easier than ever to build stack classes in Python.
After declaring the class, add a container to hold items in the stack. For this we may need to create internal variables:
class stack: def __init__(self): self.__index = []
After starting the stacking class, the __index variable will be initialized as an empty list. The list will later have the items in our stack.
Step1: len() Function Set Up
In this step, we will set up the len () function. To make our stack class work with the len() function, we need to define a special method, also called a Dunder (double-underscore) method. Dunder methods let us customize the behavior of built-in Python operations. For our stack, we can use the len() Dunder method to implement the “length” behavior we want:
class stack: def __init__(self): self.__index = [] def __len__(self): return len(self.__index) Now, when we type len(stack_instance), it will return the item numbers in our __index variable. >>> s = stack() >>> # some additional stack operations go here >>> len(s) # fetch number of items in the stack 2
Step 2: Setting up the .push() method
To implement our .push() method that will store items in our __index variable, we need to decide which “end” of the list we should use to insert our items. You might think that appending items to our __index list are a good idea since we usually consider the highest-indexed item to be the “top”.
However, this approach has some drawbacks for our purposes. This is because our reference, the “top” index, will keep changing as we manipulate our stack. Also, this value would have to be recalculated every time we use it. It is more efficient to add and remove items from the “beginning” of our list since the index of the “beginning” never changes. It will always be zero.
Therefore, our __index variable will have the “top” item as the first item of our list. Since we are using a Python list, we can do this with the built-in .insert() method:
class stack: def __init__(self): self.__index = [] def __len__(self): return len(self.__index) def push(self,item): self.__index.insert(0,item)
Step 3: Setting up the .peek() method
Setting up the .peek() method is very simple. It returns the stack’s “top” value, which is the first item in our list, __index[0]. But, we need to consider the case that our list is empty. We will want to check our stack with the len() function and raise an exception if we try to use .peek() on an empty stack:
class stack:
def __init__(self):
self.__index = []
def __len__(self):
return len(self.__index)
def push(self,item):
self.__index.insert(0,item)
def peek(self):
if len(self) == 0:
raise Exception("peek() called on empty stack.")
return self.__index[0]
Step 4: Setting up the .pop() method
The .pop() method is very similar to the .peek() method, except that it also removes the returned item from the stack. Like .peek(), we need to check for an empty list before trying to return a value:
class stack:
def __init__(self):
self.__index = []
def __len__(self):
return len(self.__index)
def push(self,item):
self.__index.insert(0,item)
def peek(self):
if len(self) == 0:
raise Exception("peek() called on empty stack.")
return self.__index[0]
def pop(self):
if len(self) == 0:
raise Exception("pop() called on empty stack.")
return self.__index.pop(0)
Step 5: Setting up the str() function
Using the str() function, we can interpret Python about how we want the stack to be printed. Using it will provide the following outcomes:
>>> s = stack()
>>> print(str(s))
'<__main__.stack object at 0x000002296C8ED160>'
To display the contents of our stack in a more useful way, we can use the str() Dunder method. This method allows us to customize the output of the print() function when we print our stack object:
class stack:
def __init__(self):
self.__index = []
def __len__(self):
return len(self.__index)
def push(self,item):
self.__index.insert(0,item)
def peek(self):
if len(self) == 0:
raise Exception("peek() called on empty stack.")
return self.__index[0]
def pop(self):
if len(self) == 0:
raise Exception("pop() called on empty stack.")
return self.__index.pop(0)
def __str__(self):
return str(self.__index)
Step 6: Using the Stack
We have created a stack class that has all the features we wanted. The code below shows how we can use our custom class:
>>> s = stack()
>>> s.peek() # stack = []
Exception: peek() called on empty stack.
>>> len(s)
0
>>> s.push(5) # stack = [5]
>>> s.peek()
5
>>> s.push('Apple') # stack = ['Apple',5]
>>> s.push({'A':'B'}) # stack = [{'A':'B'},'Apple',5]
>>> s.push(25) # stack = [25,{'A':'B'},'Apple',5]
>>> len(s)
4
>>> str(s)
"[25, {'A': 'B'}, 'Apple', 5]"
>>> s.pop() # stack = [{'A':'B'},'Apple',5]
25
>>> s.pop() # stack = ['Apple',5]
{'A': 'B'}
>>> str(s)
"['Apple', 5]"
>>> len(s)
2
Different Ways to Implement Stack in Python
There are three major ways to implement stack in Python: list, Collections.deque and queue.LifoQueue. So, let’s understand them in brief:
#1 Stack Implementation using List in Python
Implementing a stack using the list in Python is relatively the most straightforward program. All you need is a Phyton code:
# Python program to
# demonstrate stack implementation
# using list
stack = []
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
#2 Implementation using collections.deque:
Another way to create a Python stack is to use the deque class from the collections module. Deque is a better choice than list when we want faster append and pop operations from both ends of the container, because deque has a constant O(1) time complexity for these operations, while list has a linear O(n) time complexity.
# Python program to
# demonstrate stack implementation
# using collections.deque
from collections import deque
stack = deque()
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack:')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
#3 Implementation using queue module
Queue in Python also follows a LIFO order, which means it is essentially a Stack. We can use the put() function to insert data into the Queue and the get() function to remove data from the Queue.
# Python program to
# demonstrate stack implementation
# using queue module
from queue import LifoQueue
# Initializing a stack
stack = LifoQueue(maxsize=3)
# qsize() show the number of elements
# in the stack
print(stack.qsize())
# put() function to push
# element in the stack
stack.put('a')
stack.put('b')
stack.put('c')
print("Full: ", stack.full())
print("Size: ", stack.qsize())
# get() function to pop
# element from stack in
# LIFO order
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())
print("\nEmpty: ", stack.empty())
Conclusion
You have now mastered the core functions of a stack class in Python. You can easily extend this implementation with more functions if you wish. This tutorial will be a solid foundation for developing your own stack implementation.
