Auxiliary stacks

What is a stack?

A stack is a collection where you add and remove from the same end, called the top. Push means add an item; pop means remove the top item; peek means read the top without removing it. The last item added is the first removed. This order is called last in, first out, or LIFO.

Example: Push 4, then 8, then 15. The next pop returns 15. After that, the top is 8.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays

Understand the idea

An auxiliary stack stores summaries that would be expensive to recompute. A minimum stack records the minimum at each depth, allowing pop to restore the previous minimum.

Work through an example

Push 5,2,4: summary minima are 5,2,2. Pop 4 retains min 2; pop 2 restores min 5.

Time and space complexity

O(1) per operation/O(n) storage when each entry stores its prefix minimum.

Why it works

At depth d, the summary equals the minimum of the first d values.

Common mistakes

Duplicate minima need counts or per-depth summaries.
One global minimum cannot recover the old answer after pop.

Chapter lab · Python implementation

A stack preserves last-in-first-out order. The lab resolves next-warmer-day queries using a monotonic stack of unresolved indices. Each index is pushed once and popped at most once. This explains why a nested while loop can still do linear total work.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def valid_brackets(text):
    stack=[]
    pairs={')':'(',']':'[','}':'{'}
    for char in text:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop()!=pairs[char]:
                return False
        else:
            raise ValueError('brackets only')
    return not stack

def warmer(temperatures):
    answer=[0]*len(temperatures)
    stack=[]
    for i,temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]]<temp:
            j=stack.pop()
            answer[j]=i-j
        stack.append(i)
    return answer

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert valid_brackets('([])')
assert not valid_brackets('([)]')
assert valid_brackets('')
assert warmer([73,71,74])==[2,1,0]
assert warmer([5,5,5])==[0,0,0]

CHECK YOUR UNDERSTANDING