Stacks: last in, first out

Last in, first out

A stack is a collection with one strict rule about order: the last item you put in is the first one you take out. That rule has a short name, LIFO, for last in, first out. A stack does not let you reach into the middle; you only ever touch the top.

The everyday picture is a pile of plates. You add a clean plate to the top, and when you need one you take it from the top too. The plate at the bottom went in first and comes out last. If you want a plate from lower down, you have to lift off the ones above it first. That single access point, the top, is the whole idea.

Two operations do everything. Push puts an item on the top. Pop takes the top item off and hands it back. Because both act only on the top, a stack never asks "which position?", which is what makes it fast and simple.

Building a stack from a list

You do not need anything new to make a stack. A Python list already has the two methods you want: .append() adds to the end, and .pop() removes from the end. Treat the end of the list as the top of the stack and you are done:

stack = []
stack.append("eat")     # push
stack.append("sleep")   # push
stack.append("code")    # push

print(stack.pop())      # code   (last in, first out)
print(stack.pop())      # sleep
print(stack.pop())      # eat

Notice the items come out in the exact reverse of the order they went in. One caution: popping from an empty stack raises an error, so a careful program checks first, often with if stack: or by testing len(stack) before it pops.

Where stacks show up

Stacks are quietly everywhere once you know the shape:

• The back button in a web browser. Each page you visit is pushed onto a stack. Pressing back pops the current page and returns you to the previous one, in reverse order of your visits.
• The undo command in an editor. Each change is pushed as it happens. Undo pops the most recent change and reverses it, which is why undo always walks backwards through your edits.
• A program's own call stack, which tracks the functions that are currently running so it knows where to return when each one finishes.

Every one of these needs the same thing: come back to the most recent item first. That is a stack, whatever it is called in the application.

A worked example: is a word a palindrome?

A palindrome reads the same forwards and backwards, like "level" or "radar". A stack gives a tidy way to check one, because pushing every letter and then popping them all yields the word reversed:

def is_palindrome(word):
    stack = []
    for letter in word:
        stack.append(letter)   # push every letter

    reversed_word = ""
    while stack:
        reversed_word = reversed_word + stack.pop()   # pop rebuilds it backwards

    return word == reversed_word

print(is_palindrome("level"))   # True
print(is_palindrome("python"))  # False

The first loop pushes each letter, so the last letter of the word ends up on top. The while stack: loop then pops until the stack is empty, and because pop takes the top each time, the letters come out in reverse. If the reversed spelling matches the original, the word is a palindrome. The LIFO rule did the reversing for you, with no index juggling at all.

Prefer to see it explained? Here is the recorded Code for Albania lecture on this topic.

Check yourself

1. State the LIFO rule in one sentence, and explain why a browser's back button behaves exactly like it.
2. A stack built on a Python list uses .append() to push and .pop() to take the top item. What happens if you pop from an empty stack, and how would you guard against it?
3. In the palindrome example, what is on top of the stack right after the first loop finishes, and why does popping from there rebuild the word in reverse?