Spaces:
Sleeping
Sleeping
File size: 5,601 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | STACK AND QUEUE
===============
--- STACK ---
LIFO — Last In First Out. Think of a stack of plates.
Operations: push (add), pop (remove top), peek (view top). All O(1).
Uses: undo/redo, function call stack, expression evaluation, DFS, balanced brackets.
# Stack using Python list
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek()) # 30
print(s.pop()) # 30
print(s.size()) # 2
--- Balanced Brackets using Stack ---
Check if brackets (, ), {, }, [, ] are balanced.
def is_balanced(expr):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in expr:
if ch in '({[':
stack.append(ch)
elif ch in ')}]':
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("({[]})")) # True
print(is_balanced("({[})")) # False
print(is_balanced("((()))")) # True
--- Next Greater Element using Stack ---
For each element, find the next element greater than it.
Time: O(n). Space: O(n).
def next_greater(arr):
n = len(arr)
result = [-1] * n
stack = [] # stores indices
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
return result
print(next_greater([4, 5, 2, 25])) # [5, 25, 25, -1]
--- Evaluate Postfix Expression ---
Postfix: operands come before operator (e.g. "2 3 +" = 5).
def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token.lstrip('-').isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(int(a / b))
return stack[0]
print(evaluate_postfix("2 3 1 * + 9 -")) # Output: -4
--- Min Stack ---
Stack that supports getMin() in O(1).
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def get_min(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(5); ms.push(3); ms.push(7); ms.push(2)
print(ms.get_min()) # 2
ms.pop()
print(ms.get_min()) # 3
--- QUEUE ---
FIFO — First In First Out. Think of a line at a ticket counter.
Operations: enqueue (add rear), dequeue (remove front), peek. All O(1).
Uses: BFS, scheduling, print queues, sliding window.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items.popleft()
def peek(self):
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue()) # 10
print(q.peek()) # 20
--- Circular Queue ---
Fixed-size queue where rear wraps around to front.
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.front = self.rear = -1
self.capacity = capacity
self.size = 0
def enqueue(self, item):
if self.size == self.capacity:
raise OverflowError("Queue is full")
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
if self.front == -1:
self.front = 0
self.size += 1
def dequeue(self):
if self.size == 0:
raise IndexError("Queue is empty")
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
--- Deque (Double-Ended Queue) ---
Insert and delete from both ends in O(1).
from collections import deque
d = deque()
d.appendleft(1) # add to front
d.append(2) # add to rear
d.appendleft(0)
print(d) # deque([0, 1, 2])
d.popleft() # remove from front → 0
d.pop() # remove from rear → 2
print(d) # deque([1])
--- Priority Queue ---
Elements are dequeued based on priority, not insertion order.
Python's heapq is a min-heap by default.
import heapq
pq = []
heapq.heappush(pq, (3, 'low'))
heapq.heappush(pq, (1, 'high'))
heapq.heappush(pq, (2, 'medium'))
print(heapq.heappop(pq)) # (1, 'high')
print(heapq.heappop(pq)) # (2, 'medium')
# Max-heap: negate priorities
heapq.heappush(pq, (-5, 'top priority'))
print(heapq.heappop(pq)) # (-5, 'top priority')
--- Difference: Stack vs Queue ---
Stack: LIFO — last added is first removed. Uses: DFS, backtracking, undo.
Queue: FIFO — first added is first removed. Uses: BFS, scheduling, buffering.
|