Hello in this tutorial, we will understand stack in Python programming.
1. Introduction
In Python, a stack is a data structure that follows the Last-In, First-Out (LIFO) principle. It is an abstract data type that represents a collection of elements with two main operations: “push” and “pop.” A stack can be visualized as a stack of plates, where you can only add or remove plates from the top. The plate that is added last will be the first one to be removed.
1.1 What is LIFO principle?
The LIFO principle, also known as “Last-In, First-Out,” is a basic concept in computer science and data structures. It describes the behavior of certain data structures, such as stacks, where the last item inserted (pushed) into the structure is the first one to be removed (popped) from it.
In a LIFO data structure, new elements are added to the top, and removal or retrieval operations are performed on the topmost element. This creates a “stack” of elements, resembling a physical stack of objects, where you can only access the topmost item without disturbing the items below it.
Consider a stack of plates. When you add a new plate to the stack, it goes on top of the existing plates. If you want to remove a plate, you would remove the topmost plate first. Similarly, in a LIFO data structure like a stack, the most recently added element is the one that is accessible and removable.
The LIFO principle is used in various contexts, including:
- Function call stack: When a function is called, its information is pushed onto the call stack, and when the function finishes, it is popped off the stack.
- Undo/Redo functionality: Actions performed in reverse order can be stored in a stack, allowing for undoing operations.
- Expression evaluation: In certain algorithms, like postfix notation evaluation, stacks are used to store and manipulate operands and operators.
By following the LIFO principle, you can efficiently manage the order of elements and implement operations that involve adding and removing items from the top of a stack-like structure.
1.2 Common use-cases
Stacks have various common use cases in computer science and programming. Here are some of the most common use cases for stacks:
- Function call stack: Stacks are used to manage function calls in programming languages. When a function is called, its information, including the return address and local variables, is pushed onto the call stack. When the function completes execution, it is popped off the stack, and the control returns to the calling function.
- Expression evaluation: Stacks are utilized in evaluating expressions, especially in cases where the order of operations needs to be maintained. For example, in postfix notation evaluation, also known as Reverse Polish Notation (RPN), a stack is used to store operands and perform operations in the correct order.
- Balancing parentheses and checking syntax: Stacks can be used to ensure the balanced and correct usage of parentheses, braces, and brackets in programming languages. Each opening symbol is pushed onto the stack, and when a closing symbol is encountered, it is checked against the top element of the stack. If they match, the opening symbol is popped off the stack, indicating the correct syntax.
- Undo/Redo functionality: Stacks are employed in implementing undo and redo functionality in applications. Each action performed is pushed onto the stack, allowing for easy undoing of the most recent action by popping it from the stack. Redo operations can be achieved by maintaining a separate redo stack.
- Backtracking in algorithms: Stacks can be used to implement backtracking algorithms, where decisions can be reversed by popping elements from the stack and exploring alternative paths. This is commonly seen in algorithms like depth-first search (DFS) and backtracking in solving problems like maze traversal or finding a path.
- Browser history: Stacks can be used to maintain browser history, where each visited webpage is pushed onto the stack. The “back” button pops the topmost page from the stack, simulating navigation through previously visited pages.
These are just a few examples of the many use cases for stacks. Stacks are versatile data structures that provide a simple and efficient way to manage the order of elements and implement various algorithms and functionalities.
2. Implementation
2.1 Implementing stack using List
In this example, a Stack class is defined with the specified methods to manipulate the stack. The stack is implemented using a Python list. You can see how to push elements onto the stack, pop elements from the stack, peek at the top element, check if the stack is empty, access the top element, and determine the size of the stack.
Code example
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# Practical example using a stack:
# Creating a stack object
stack = Stack()
# Pushing elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)
stack.push(40)
# Checking if the stack is empty
print("Is the stack empty?", stack.is_empty())
# Accessing the top element of the stack
print("The top element of the stack:", stack.peek())
# Popping elements from the stack
print("Popped element:", stack.pop())
print("Popped element:", stack.pop())
# Checking the size of the stack
print("Size of the stack:", stack.size())
Run the file and if everything goes well the following output will be logged in the IDE console.
Console output
Is the stack empty? False The top element of the stack: 40 Popped element: 40 Popped element: 30 Size of the stack: 2
2.2 Implementing stack using Dequeue
In this example, the Stack class is defined using the deque class from the collections module. The deque provides an efficient implementation for the stack. The methods for manipulating the stack are implemented accordingly, including push, pop, peek, checking if the stack is empty, accessing the top element, and determining the size of the stack.
Code example
from collections import deque
class Stack:
def __init__(self):
self.stack = deque()
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# Practical example using a stack:
# Creating a stack object
stack = Stack()
# Pushing elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)
stack.push(40)
# Checking if the stack is empty
print("Is the stack empty?", stack.is_empty())
# Accessing the top element of the stack
print("The top element of the stack:", stack.peek())
# Popping elements from the stack
print("Popped element:", stack.pop())
print("Popped element:", stack.pop())
# Checking the size of the stack
print("Size of the stack:", stack.size())
Run the file and if everything goes well the following output will be logged in the IDE console.
Console output
Is the stack empty? False The top element of the stack: 40 Popped element: 40 Popped element: 30 Size of the stack: 2
That is all for this tutorial and I hope the article served you with whatever you were looking for. Happy Learning and do not forget to share!
3. Conclusion
In conclusion, a stack is a fundamental data structure that follows the Last-In, First-Out (LIFO) principle. It is commonly used in various programming scenarios to manage the order of elements and implement specific functionalities efficiently.
In Python, a stack can be implemented using a list or the deque class from the collections module. The stack operations such as push, pop, peek, checking if the stack is empty, accessing the top element, and determining the size can be implemented using these data structures.
Stacks have several practical use cases, including managing function calls in programming languages, evaluating expressions while maintaining the order of operations, ensuring balanced syntax with parentheses and brackets, implementing undo/redo functionality, supporting backtracking in algorithms, and maintaining browser history.
Understanding stacks and their operations can be beneficial in designing algorithms, solving problems, and implementing specific functionalities in programming.
You can download the source code from the Downloads section.
4. Download the Project
This was a tutorial on how to implement stack in Python programming.
You can download the full source code of this example here: Stack in Python
