Difficulty: Advanced
Stacks and queues are abstract data types that define specific rules for how elements are added and removed. They are foundational to many algorithms and appear frequently in coding interviews.
A stack follows the Last-In, First-Out (LIFO) principle. The last element added is the first one removed. Think of a stack of plates: you add to the top and remove from the top. The core operations are push (add to top), pop (remove from top), and peek (view the top without removing). In Python, a regular list works efficiently as a stack using append() for push and pop() for pop, both of which are O(1) operations.
A queue follows the First-In, First-Out (FIFO) principle. The first element added is the first one removed, like a line at a ticket counter. The core operations are enqueue (add to back) and dequeue (remove from front). Using a Python list for a queue is inefficient because list.pop(0) is O(n) since all remaining elements must be shifted. Instead, Python provides collections.deque (double-ended queue), which supports O(1) append and popleft operations.
Stacks have many practical applications: function call management (the call stack), undo/redo functionality, expression evaluation and syntax parsing, depth-first search (DFS), and balancing parentheses. Queues are used in breadth-first search (BFS), task scheduling, print spooling, and buffering.
Python's collections.deque is versatile and can be used as both a stack and a queue. It supports append/pop from both ends in O(1). You can also create a bounded deque with a maxlen parameter, which automatically discards elements from the opposite end when the deque is full. For thread-safe queue operations, Python provides the queue.Queue class.
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print("Stack:", stack)
top = stack.pop()
print("Popped:", top)
print("Stack after pop:", stack)
print("Peek:", stack[-1])
print("Is empty:", len(stack) == 0)Python lists support O(1) append and pop from the end, making them suitable as stacks. Peek is done by accessing the last element with index -1.
from collections import deque
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
print("Queue:", list(queue))
front = queue.popleft()
print("Dequeued:", front)
print("Queue after dequeue:", list(queue))
print("Front:", queue[0])
print("Size:", len(queue))deque provides O(1) append to the right and popleft from the left, making it the ideal queue implementation in Python. Using list.pop(0) would be O(n).
def is_balanced(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in '([{':
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("({[]})"))
print(is_balanced("([)]"))
print(is_balanced("{{}}"))
print(is_balanced("("))Opening brackets are pushed onto the stack. When a closing bracket is encountered, we check if the top of the stack has the matching opening bracket. If the stack is empty at the end, all brackets were balanced.
from collections import deque
recent = deque(maxlen=3)
for i in range(1, 6):
recent.append(i)
print(f"Added {i}: {list(recent)}")A deque with maxlen automatically discards the oldest element when a new one is added beyond the limit. This is useful for maintaining a sliding window of recent items.
stack, queue, collections.deque