Stack
The stack is a basic container-type abstract data structure that retrieves items based on the LIFO(Last in First Out) order. Stacks are simple to implement but also very efficient.
A basic stack must support three basic operations in constant time:
- Push(O(1)) — Insert an item to the top of the stack.
- Pop(O(1)) — Return and remove the item at the top of the stack.
- Peek(O(1)) — Return the item at the top of the stack.
Another helpful operation that most stack implement is the is_empty() operation which return True or False if the stack is empty or not. As we can see, all the operations that a stack implements takes constant time. Surprisingly, we can perform many types of tasks efficiently using these simple, constant time operations.
Implementing a Stack
1. Push
First, let’s implement a basic stack by adding the method push:
class Stack:
def __init__(self, stack = None, stack_size = 0):
"""
Constructor #1 for Stack class
"""
self.stack = []
self.stack_size = stack_size
def push(self, item):
"""
Push item to the top of the stack
"""
self.stack.append(item)
self.stack_size += 1
def __repr__(self):
"""
Return a string representation of the stack
"""
return f"Stack: {self.stack}"
if __name__ == "__main__":
# Creating an empty stack
stack = Stack()
# Pushing 4 items
stack.push(1)
stack.push(3)
stack.push(5)
stack.push(2)
# Printing stack
print(stack)
# Output:
# Stack: [1, 3, 5, 2]We can improve the construction of the stack by adding a class method that will create a stack from a given list of items:
class Stack:
def __init__(self, stack = None, stack_size = 0):
"""
Constructor #1 for Stack class
"""
self.stack = []
self.stack_size = stack_size
def push(self, item):
"""
Push item to the top of the stack
"""
self.stack.append(item)
self.stack_size += 1
def __repr__(self):
"""
Return a string representation of the stack
"""
return f"Stack: {self.stack}"
@classmethod
def generate_stack(cls, *args):
"""
Constructor #2 for Stack class. Generates a stack from a list of items
"""
stack = cls()
stack.stack.extend(args)
stack.stack_size = len(args)
return stack
if __name__ == "__main__":
# Create stack
stack = Stack.generate_stack(1,3,5,2)
# Print stack
print(stack)
# Output:
# Stack: [1, 3, 5, 2]2. Pop
Next, let’s implement the pop method:
class Stack:
def __init__(self, stack = None, stack_size = 0):
"""
Constructor #1 for Stack class
"""
self.stack = []
self.stack_size = stack_size
def push(self, item):
"""
Push item to the top of the stack
"""
self.stack.append(item)
self.stack_size += 1
def __repr__(self):
"""
Return a string representation of the stack
"""
return f"Stack: {self.stack}"
@classmethod
def generate_stack(cls, *args):
"""
Constructor #2 for Stack class. Generates a stack from a list of items
"""
stack = cls()
stack.stack.extend(args)
stack.stack_size = len(args)
return stack
def pop(self, index=None):
"""
If no index given, remove item from top of the stack
"""
self.stack_size -= 1
if index is not None:
return self.stack.pop(index)
else:
return self.stack.pop()
if __name__ == "__main__":
stack = Stack.generate_stack(1,3,5,2)
print(stack)
# Remove last item
stack.pop()
# Remove first item
stack.pop(0)
# print stack
print(stack)
# Output:
# Stack: [1, 3, 5, 2]
# Stack: [1, 3]3. Peek and is_empty
Finally, the last two methods to complete our basic stack is the peek and is_empty methods:
class Stack:
def __init__(self, stack = None, stack_size = 0):
"""
Constructor #1 for Stack class
"""
self.stack = []
self.stack_size = stack_size
def push(self, item):
"""
Push item to the top of the stack
"""
self.stack.append(item)
self.stack_size += 1
def __repr__(self):
"""
Return a string representation of the stack
"""
return f"Stack: {self.stack}"
@classmethod
def generate_stack(cls, *args):
"""
Constructor #2 for Stack class. Generates a stack from a list of items
"""
stack = cls()
stack.stack.extend(args)
stack.stack_size = len(args)
return stack
def pop(self, index=None):
"""
If no index given, remove item from top of the stack
"""
self.stack_size -= 1
if index:
return self.stack.pop(index)
else:
return self.stack.pop()
def peek(self):
"""
Return the top item of the stack
"""
return self.stack[-1]
def is_empty(self):
"""
Check if stack is empty
"""
return True if self.stack_size == 0 else False
if __name__ == "__main__":
# Create a stack
stack = Stack.generate_stack(1,3,5,2)
# Check the item at the top of the stack
print(stack.peek())
# Output:
# 2Example
To make this more concrete, let’s check out an example of how to use this data structure to solve a task. For example, let’s solve the following Leetcode problem using a stack:
In short, we are given a string of brackets(for example, “([[{}]])”) and we need to figure out if their order is valid.
Stacks are perfect for these types of problems.
The basic idea is to use a stack to keep track of the opening brackets while traversing the string from left to right.
- When we encounter an opening bracket, we push it onto the stack.
- When we encounter a closing bracket, we check if it matches the top bracket on the stack and pop it if it does.
My solution looks like this:
def check_brackets(s):
"""
Return True if a string of brackets is balanced. False if not.
"""
# Set a dictionary of bracket pairs
pairs = {
'(':')',
'[':']',
'{':'}'
}
# Create an empty stack
stack = Stack()
# Initlaize algorithm
for bracket in s:
# If brack is ( , [ or {. Add bracket to stack
if bracket in pairs.keys():
stack.push(bracket)
# if stack is not empty and bracket is ), ] or }. Remove it from stack
elif not stack.is_empty():
if bracket in pairs[stack.pop()]:
continue
else:
return False
# If brackets are vaild, the stack should be empty
return True if stack.stack_size == 0 else False
# Solve problem
s = "([[{}]])"
check_brackets(s)
# Output:
# TrueAs we can see, we were able to solve this problem in O(n). Choosing the right data structure is key to solving problems efficiently.
Note that choosing to use a stack is not the only way to solve this problem. We could have also used a queue or an array. However, the stack is a more natural choice for this problem. Choosing the more natural data structure will make your code more readable and easier to understand.
