How to Create a Stack in Python

How to Create a Stack in Python

How to Create a Stack in Python: A Complete Guide

Stacks are one of the fundamental data structures in computer science, widely used for solving problems in various domains such as algorithms, memory management, and undo functionality in applications. This blog post will guide you through the process of creating and implementing a stack in Python, complete with code examples and explanations.

What Is a Stack?

A stack is a linear data structure that follows the **Last In, First Out (LIFO)** principle. This means that the last item added to the stack is the first one to be removed. Think of it like a stack of plates: the plate added last is the one you pick up first.

Stacks have two main operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the element at the top of the stack.

Other commonly used operations include:
- Peek/Top: Returns the element at the top of the stack without removing it.
- IsEmpty: Checks if the stack is empty.
- Size: Returns the number of elements in the stack.

Applications of Stacks

Stacks are used in:
- Expression evaluation: Converting infix expressions to postfix or prefix.
- Backtracking: Navigating through paths, like in maze-solving algorithms.
- Undo functionality: Keeping track of actions in applications.
- Function call management: Managing function calls in recursion.

Creating a Stack in Python

Python does not have a built-in stack data structure, but you can implement one using:
1. A Python list.
2. The `collections.deque` module.
3. A custom class.

Let’s explore each approach in detail.

1. Stack Implementation Using a Python List

Python lists can be used as stacks because they support operations like appending and removing elements from the end.

class Stack:
   def __init__(self):
       self.items = []
   def push(self, item):
       self.items.append(item)
   def pop(self):
       if not self.is_empty():
           return self.items.pop()
       else:
           raise IndexError("Pop from an empty stack")
   def peek(self):
       if not self.is_empty():
           return self.items[-1]
       else:
           raise IndexError("Peek from an empty stack")
   def is_empty(self):
       return len(self.items) == 0
   def size(self):
       return len(self.items)
# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack after pushes:", stack.items)
print("Top element:", stack.peek())
print("Popped element:", stack.pop())
print("Stack after pop:", stack.items)

Advantages:
- Simple and easy to implement.

Disadvantages:
- Lists are not optimized for stack operations, as they can cause overhead in large-scale applications.

 2. Stack Implementation Using `collections.deque`

The `collections.deque` (double-ended queue) module is optimized for stack operations and is faster than lists.

from collections import deque
class Stack:
   def __init__(self):
       self.items = deque()
   def push(self, item):
       self.items.append(item)
   def pop(self):
       if not self.is_empty():
           return self.items.pop()
       else:
           raise IndexError("Pop from an empty stack")
   def peek(self):
       if not self.is_empty():
           return self.items[-1]
       else:
           raise IndexError("Peek from an empty stack")
   def is_empty(self):
       return len(self.items) == 0
   def size(self):
       return len(self.items)
# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Stack after pushes:", list(stack.items))
print("Top element:", stack.peek())
print("Popped element:", stack.pop())
print("Stack after pop:", list(stack.items))

Advantages:
- Optimized for append and pop operations.
- Faster than lists for stack-like behavior.

3. Stack Implementation Using a Custom Class

You can create a fully custom stack implementation to better understand its working or to tailor it to specific requirements.

class Node:
   def __init__(self, value):
       self.value = value
       self.next = None
class Stack:
   def __init__(self):
       self.top = None
       self.count = 0
   def push(self, item):
       new_node = Node(item)
       new_node.next = self.top
       self.top = new_node
       self.count += 1
   def pop(self):
       if self.is_empty():
           raise IndexError("Pop from an empty stack")
       removed_value = self.top.value
       self.top = self.top.next
       self.count -= 1
       return removed_value
   def peek(self):
       if self.is_empty():
           raise IndexError("Peek from an empty stack")
       return self.top.value
   def is_empty(self):
       return self.top is None
   def size(self):
       return self.count
# Example usage
stack = Stack()
stack.push(100)
stack.push(200)
stack.push(300)
print("Top element:", stack.peek())
print("Popped element:", stack.pop())
print("Stack size:", stack.size())

Advantages:
- Full control over implementation.
- Can include additional features as needed.

Disadvantages:
- More complex to implement than using lists or `deque`.

Which Implementation Should You Choose?

- Use **Python lists** for simple and small-scale applications.
- Use **`collections.deque`** for performance-critical applications.
- Use a **custom implementation** if you need more control or are working with linked list-based data structures.

Conclusion

In this guide, we explored what stacks are, their applications, and how to implement them in Python using three different approaches. Stacks are versatile and essential for many programming tasks, so mastering their implementation will improve your problem-solving skills.

Now that you’ve learned how to create a stack in Python, try building a real-world application like an undo/redo feature or an expression evaluator to solidify your understanding!

Tags

Share