What is Stack Data Structure? It's implementation in a Pythonic Way.
Lets understand every aspects of Stack data structure.
Before grinding to learn something, let's get some motivation:
"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."
- Linus Torvalds
If you are a developer or even a student, you have heard the term Stack somewhere. It is one of the most important aspects of a data structure in programming. If you ever wondered what stacks are, how they work, and why they even exist, then this blog is for you.
By the end of the blog, you’ll know:
What the heck does stack mean?
How stack operations can be performed?
How to implement it in Python?
What are the real-world applications of a stack?
This blog assumes that you know how to define Python classes and work with lists and dictionaries.
1. What is Data Structure?
Before understanding the stack let's first understand what data structures are. A data structure is a way of organizing and storing data in a computer's memory or storage system. It provides a means to efficiently manipulate and access the data. Data structures can be classified into various types, such as arrays, linked lists, stacks, queues, trees, and graphs, each with its own set of operations and characteristics.
In this article, we will be learning Stack data structure.
2. What is Stack?
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It is like a physical stack of objects, where the last object placed on top is the first one to be removed.
3. Operations Performed on Stack?
The main operations on a Stack are given below:
Push
Pop
Let's understand them one by one.
a. Push
In a stack data structure, the push operation refers to the process of adding an element to the top of the stack. The new element becomes the most recently added item and is placed above all existing elements.
b. Pop
In a stack data structure, the pop operation refers to the process of removing the topmost element from the stack. The element that is popped is also returned as the result of the operation. After the pop operation, the stack is modified, and the element that was below the popped element becomes the new top of the stack.
4. Implementation in Python
As an engineer, I think that only theoretical knowledge is not good enough for understanding any concept we also need to implement that concept practically. In this blog, I am going to implement the stack data structure using Python programming language because it will be easy to understand and implement. You can also implement it in programming languages like C and C++ which give you more insights into the stack.
The implementation which I am going to do will be the static implementation of the stack because we are going to pre-define the maximum size of the stack. As in theory, we have already seen the different operations performed on the stack, we are going to implement each operation based on their pseudo code. I assume that you are already familiar with classes in Python.
Let's first create a class with a name Stack and also create a constructor of that class:
# simplestack.py
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
As we can see in the above code snippet, inside the constructor we initialize two variables one is maxsize which is for setting the maximum size of the stack and another is items which is a list for storing elements of a stack.
Now, all the operations that can be performed on the stack are implemented using methods of Stack class.
a) Push
First, we check if the stack is full or not if the stack is not full then we insert an item into the stack. So for this first, we are going to implement a method that checks whether the stack is full or not. We are going to continue with the above code simplestack.py:
# simplestack.py
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
isFull() method first checks whether the length of the item list is equal to maxsize of the stack. If they are equal it returns True otherwise it returns False.
We can raise an error during the push operation if the stack is full. For that, we going to add a class with the name StackFullError inside simplestack.py file:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
Now, we are ready to implement the push method inside Stack class:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
As in above, we can see that the push method takes an element as a function argument, and then inside the push method if the stack is full it raises a custom exception created by us else it adds an element to the stack by calling append function and the method return an item that we had pushed to the stack.
b) Pop
First, we check if the stack is empty or not, if the stack is not empty then we pop a top element of the stack. So for this first, we are going to implement a method that checks whether the stack is empty or not. We are going to continue with the above code simplestack.py:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def isEmpty(self):
'''To check whether the stack is empty or not'''
if len(self.items) == 0:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
isEmpty() method first checks whether the length of the item list is equal to 0. If it is equal to 0, it returns True otherwise it returns False.
We can raise an error during the pop operation if the stack is empty. For that, we going to add a class with the name EmptyStackError inside simplestack.py file:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class EmptyStackError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def isEmpty(self):
'''To check whether the stack is empty or not'''
if len(self.items) == 0:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
Now, we are ready to implement the pop method inside Stack class:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class EmptyStackError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def isEmpty(self):
'''To check whether the stack is empty or not'''
if len(self.items) == 0:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
def pop(self):
'''Pop operation'''
if self.isEmpty():
raise EmptyStackError("Oops! Stack is empty: cannot pop an empty stack")
item = self.items[len(self.items) - 1]
del self.items[len(self.items) - 1]
print(f'Top element {item} is deleted')
return item
As in above, we can see inside the pop method if the stack is empty it raises a custom exception created by us else it first stores a top element of the stack on a variable item and delete the top element and the method return the item that we just deleted.
c) Top element
If you want to get the top element of the current stack, you can also get that, let's add a method with the name top_element inside Stack class in simplestack.py file:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class EmptyStackError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def isEmpty(self):
'''To check whether the stack is empty or not'''
if len(self.items) == 0:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
def pop(self):
'''Pop operation'''
if self.isEmpty():
raise EmptyStackError("Oops! Stack is empty: cannot pop an empty stack")
item = self.items[len(self.items) - 1]
del self.items[len(self.items) - 1]
print(f'Top element {item} is deleted')
return item
def top_element(self):
''' Returns top element of the stack '''
if self.isEmpty():
raise EmptyStackError("Oops! Stack is empty")
top = self.items[len(self.items) - 1]
return top
Inside the top_element method we first check whether the stack is empty or not, if it is empty then we raise an empty stack error else we access the top element of the stack using list indexing and return the top element.
d) All elements
To print all elements of the stack we are going to add a method with the name all_elements inside Stack class in simplestack.py file:
# simplestack.py
class StackFullError(Exception):
def __init__(self, msg):
super().__init__(msg)
class EmptyStackError(Exception):
def __init__(self, msg):
super().__init__(msg)
class Stack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.items = []
def isFull(self):
'''To check whether the stack is full or not'''
if len(self.items) == self.maxsize:
return True
else:
return False
def isEmpty(self):
'''To check whether the stack is empty or not'''
if len(self.items) == 0:
return True
else:
return False
def push(self, data):
'''Push operation'''
if self.isFull():
raise StackFullError("Oops! Stack is full")
self.items.append(data)
return data
def pop(self):
'''Pop operation'''
if self.isEmpty():
raise EmptyStackError("Oops! Stack is empty: cannot pop an empty stack")
item = self.items[len(self.items) - 1]
del self.items[len(self.items) - 1]
print(f'Top element {item} is deleted')
return item
def top_element(self):
''' Returns top element of the stack '''
if self.isEmpty():
raise EmptyStackError("Oops! Stack is empty")
top = self.items[len(self.items) - 1]
return top
def all_elements(self):
print("The elements of the stack are:")
for item in self.items:
print(item)
Now, let's use this Stack class to perform stack operation:
# simplestack.py
# add it in the above code
s = Stack(5) # Stack with 5 elements
s.push(2)
s.push(12)
s.push(15)
s.push(14)
top1 = s.top_element()
print("Top element before poping: ", top1)
s.pop()
top2 = s.top_element()
print("Top element after poping: ", top2)
s.all_elements()
In the above code, we can see that we instantiate the Stack class with 5 as an argument that tells us that it can store a maximum of 5 elements. After that, we pushed four elements into the stack which are 2, 12, 15, 14. Then, we get the top element of the stack and print it on the terminal then we pop the element from the stack by calling the pop() method, to see the effect of pop we again get the top element of the stack and finally print all the elements of the current stack.
The final complete code is
The output we obtained by running simplestack.py is given below:
$ python simplestack.py
Top element before poping: 14
Top element 14 is deleted
Top element after poping: 15
The elements of the stack are:
2
12
15
5. Real World Applications
Apply, apply, apply any concept without practical application is just useless.
Stack data structures have several real-world applications. Here are a few examples:
a. Function Calls
Stacks are commonly used in programming languages to manage function calls. Each time a function is called, the program pushes the current execution context onto the stack. When the function completes, it pops the execution context from the stack, allowing the program to resume from where it left off.
b. Undo/Redo Operations
Many applications provide undo/redo functionality, such as text editors or graphic design tools. A stack can be used to keep track of the actions performed, allowing the user to undo or redo them by pushing and popping elements from the stack.
c. Web Browser History
Web browsers use a stack to store the history of visited web pages. When you click the back button, the browser pops the most recent page from the stack, allowing you to navigate back to the previous page.
d. Expression Evaluation
Stacks are useful for evaluating expressions, particularly mathematical or logical expressions. They can be used to convert infix expressions to postfix or prefix notation, making it easier to evaluate and calculate the result.
e. Compiler Syntax Parsing
Compilers and interpreters use stacks for syntax parsing. They can use a stack-based approach, such as a stack-based parsing technique called recursive descent parsing, to analyze and interpret the structure of programming language statements.
6. Conclusion
If you still have questions, don’t hesitate to reach out in the comments section below! To learn more about the stack and its implementations in Python, you can also check other contents about the stack on the internet.
This much for today; see you in the next blog. Take care! Cheers!
