A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added to the stack is the first one to be removed. It consists of two main operations: push, which adds an element to the top of the stack, and pop, which removes the top element from the stack. Additionally, there is a peek operation that allows you to view the top element without removing it. Stacks are commonly used in programming languages for function calls, as well as in algorithms such as depth-first search and backtracking. Keep reading below to learn how to use a Stack in Python.
Looking to get a head start on your next software interview? Pickup a copy of the best book to prepare: Cracking The Coding Interview!
How to use a Stack in Python with example code
A Stack is a data structure that follows the Last-In-First-Out (LIFO) principle. In Python, we can implement a Stack using a list. The list’s append() method can be used to add elements to the top of the stack, and the pop() method can be used to remove elements from the top of the stack.
Here’s an example of how to implement a Stack in Python:
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
In the above code, we define a Stack class with the following methods:
– __init__(): Initializes an empty list to store the stack elements.
– push(item): Adds an item to the top of the stack.
– pop(): Removes and returns the item at the top of the stack.
– is_empty(): Returns True if the stack is empty, False otherwise.
– peek(): Returns the item at the top of the stack without removing it.
– size(): Returns the number of elements in the stack.
Let’s see how we can use this Stack class to solve a problem. Suppose we have a string containing parentheses, brackets, and braces. We want to check if the string is balanced, i.e., if each opening symbol has a corresponding closing symbol in the correct order.
def is_balanced(s):
stack = Stack()
for symbol in s:
if symbol in '([{':
stack.push(symbol)
elif symbol in ')]}':
if stack.is_empty():
return False
top = stack.pop()
if not matches(top, symbol):
return False
return stack.is_empty()
def matches(open, close):
opens = '([{'
closes = ')]}'
return opens.index(open) == closes.index(close)
In the above code, we define a function is_balanced() that takes a string s as input and returns True if the string is balanced, False otherwise. We use a Stack to keep track of the opening symbols we encounter. If we encounter a closing symbol, we check if it matches the last opening symbol we encountered. If it does, we pop the opening symbol from the stack. If it doesn’t, we return False. If we reach the end of the string and the stack is empty, we return True.
What is a Stack in Python?
In conclusion, a stack is a fundamental data structure in computer science that is widely used in programming languages like Python. It is a collection of elements that follows the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. Stacks are commonly used in solving problems that require a temporary storage of data, such as in recursive algorithms, expression evaluation, and backtracking. In Python, stacks can be implemented using built-in data types like lists or using the deque class from the collections module. Understanding the concept of stacks and how to use them in Python can greatly enhance your programming skills and enable you to solve complex problems more efficiently.
Elevate your software skills
Ergonomic Mouse |
Custom Keyboard |
SW Architecture |
Clean Code |
