LIFO operations and implementation

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

Stacks expose push, pop, and peek at one end. Last-in-first-out matches nested work: the newest unfinished task must finish first. Python append/pop at the list end are the usual implementation.

Work through an example

Push A, push B, pop returns B, then peek returns A. No search is required for the newest item.

Time and space complexity

Amortized O(1) push; O(1) end pop/peek; O(n) storage.

Why it works

The top is the most recently pushed item not yet popped.

Common mistakes

pop on empty raises an error.
Removing from the front implements different ordering and shifts elements.

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