Stack in Python using a list

A stack is a collection where the last item you add is the first one you take out: last in, first out (LIFO). Think of a pile of plates. A Python list works as a stack.

The program

stack = []

stack.append("a")       # push
stack.append("b")
stack.append("c")
print(stack)

print(stack[-1])        # peek: look at the top without removing it
print(stack.pop())      # pop: remove and return the top
print(stack)

if stack:
    print("not empty, size", len(stack))

['a', 'b', 'c']
c
c
['a', 'b']
not empty, size 2

How it works

• The end of the list is the top of the stack. append() adds to the end, and pop() removes from the end. Both are fast, whatever the length of the list.
• stack[-1] reads the last item without removing it.
• pop() on an empty list raises an IndexError, so check if stack: first when the stack might be empty. An empty list counts as False.

Using a stack: balanced brackets

A classic use of a stack is to check that every opening bracket has a matching closing bracket in the right order. Each opening bracket is pushed. Each closing bracket must match the bracket on top of the stack:

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack    # anything left open means unbalanced

for text in ["(a + b) * [c]", "{[()]}", "(]", "((x)", "x)"]:
    print(f"{text!r}: {is_balanced(text)}")

'(a + b) * [c]': True
'{[()]}': True
'(]': False
'((x)': False
'x)': False

The last two cases are the edge cases: '((x)' leaves an open bracket on the stack, and 'x)' tries to pop from an empty stack.

Related programs: Queue in Python using deque.