Stack Basics

The Idea

A stack only lets you touch one end: the top. Push puts an item there, pop takes the newest one back off. Both are O(1) because nothing else in the pile moves. The price is that older items are buried until you clear what sits above them.

Real-World Example

A drawing app's undo history. Every stroke lands on top of the pile, and undo lifts off the most recent one. To get back to a sketch you made ten strokes ago, you have to undo the nine strokes drawn after it first.

The Code

stack = []

stack.append("a")        # push -> O(1)
stack.append("b")
stack.append("c")        # stack is ["a", "b", "c"]

print(stack[-1])         # "c"  peek: look, do not remove
print(stack.pop())       # "c"  the newest leaves first
print(stack.pop())       # "b"
print(stack)             # ["a"]
print(len(stack) == 0)   # False -> still one item left

s = []
for ch in "SUN":
  s.append(ch)
print(s.pop() + s.pop())