Use stacks to parse structures, evaluate expressions, or simulate other data structures
Push state and pop when encountering matching delimiters or operators; two stacks for operator precedence or queue emulation.
Use for parentheses validation, decoding strings, calculator problems, or building a queue from two stacks.
Delimiter matching with a single stack; two-stack decode/evaluate patterns; and queue emulation using two stacks for amortized O(1).
# Stack Simulation Templates
def is_valid_parentheses(s):
pairs={')':'(', ']':'[', '}':'{'}; st=[]
for ch in s:
if ch in '([{': st.append(ch)
else:
if not st or st[-1]!=pairs.get(ch,''): return False
st.pop()
return not st
def decode_string(s):
num_st, str_st = [], ['']
k=0
for ch in s:
if ch.isdigit(): k = k*10 + int(ch)
elif ch=='[': num_st.append(k); str_st.append(''); k=0
elif ch==']': times=num_st.pop(); seg=str_st.pop(); str_st[-1] += seg*times
else: str_st[-1]+=ch
return str_st[-1]Push on open, pop on matching close
def is_valid_parentheses(s):
st = []
mp = {')':'(', ']':'[', '}':'{'}
for ch in s:
if ch in '([{': st.append(ch)
else:
if not st or st.pop() != mp.get(ch): return False
return not stUse two stacks for numbers and ops/strings
def decode_string(s):
st_num, st_str = [], []
cur, num = '', 0
for ch in s:
if ch.isdigit():
num = num*10 + int(ch)
elif ch == '[':
st_num.append(num); st_str.append(cur)
cur, num = '', 0
elif ch == ']':
times = st_num.pop(); prev = st_str.pop()
cur = prev + cur * times
else:
cur += ch
return curIn/out stacks for amortized O(1) dequeues
class MyQueue:
def __init__(self):
self._in, self._out = [], []
def push(self, x):
self._in.append(x)
def _move(self):
if not self._out:
while self._in:
self._out.append(self._in.pop())
def pop(self):
self._move(); return self._out.pop()
def peek(self):
self._move(); return self._out[-1]
def empty(self):
return not self._in and not self._outEach char/token processed once.
Stack holds nested state.