Stacks

The most recent item comes first

A stack removes the item added most recently. Adding is called pushing, and removing is called popping. Only the top is directly available. This last-in, first-out order appears in undo histories, nested structures, expression processing, and the call stack used by recursion.

In Python, a list is a convenient stack. append adds at the top and pop removes from the top. Reading stack[-1] inspects the top without removing it. Both inspection and removal require a nonempty stack.

A complete example

Match opening and closing parentheses in a short string.

text = "(()())"
stack = []
valid = True

for ch in text:
    if ch == "(":
        stack.append(ch)
    elif not stack:
        valid = False
        break
    else:
        stack.pop()

print(valid and not stack)

True

Every opening parenthesis waits on the stack until a later closing parenthesis matches it. A closing parenthesis with no waiting opening one is invalid. After the scan, an opening parenthesis still waiting is also invalid.

This example assumes the input alphabet contains only the two parenthesis characters. If other characters are allowed, add an explicit branch for a closing parenthesis instead of treating every other character as one.

The scan performs O(n) work and uses O(n) space in the worst case. Each character is pushed at most once and popped at most once. This accounting often explains why a loop containing stack operations is still linear.

Simulate a side track

In the train exercise, arriving cars come in numerical order. To produce the next requested outgoing car, push arrivals until that car is on top, then pop it. A car below another one cannot leave until the one above leaves.

The statement guarantees that its requested order is possible. Do not assume that every permutation is possible in a different problem. For a general version, if the next required car cannot be reached at the top and no arrivals remain, the request fails.

Infix and postfix

In an infix expression, an operator sits between operands, such as a+b*c. In postfix, operands appear before the operator that uses them, giving abc*+. Postfix removes the need to infer precedence during evaluation.

To convert these exercises, output each operand immediately. For an incoming operator, pop and output operators whose precedence is greater than or equal to its precedence. Then push the incoming operator. At the end, output every remaining operator.

Multiplication and division have higher precedence than addition and subtraction. Equality matters because the exercises use left-associative operators. For a-b-c, the first subtraction must happen before the second. These statements contain no parentheses, so no parenthesis-handling extension is needed.

Common mistakes

Check that the stack is nonempty before inspecting its top. Do not use queue removal at the front, which reverses the intended discipline. Clear the stack between expressions in a multiple-case input. After reading the whole expression, remember to flush the remaining operators.

The library exercises require queue.LifoQueue. Its put and get operations provide stack behavior. Use it where requested, and use a plain list for ordinary contest code unless a different requirement applies.

Begin with the direct operation sequence, then the library version, train simulation, one expression, and several expressions. Trace a short stack after each character or car. The trace should explain every push and pop.