When we closed the previous module, TaskFlow had a task board built on linked lists, a round-robin turn rotation on circular lists, and a navigation history on a doubly linked list. And one promise was left hanging: a structure you can implement "in a few lines" because you already know how to insert and remove at the head of a linked list in O(1) — the structure that will make TaskFlow's undo possible. That structure is the stack, and this lesson introduces it as an abstract data type: what it is, what contract it offers, where it shows up constantly in your life as a programmer, and why it fits TaskFlow's undo like a glove. We won't implement anything in detail yet: first you need to understand the concept properly.

1. From the linked list to the stack
2. The LIFO principle
3. The stack ADT contract
4. How a stack works: diagram
5. Stacks in a programmer's life
6. The stack in TaskFlow: undo
7. Expected costs of the contract

In module 2 you learned that a LinkedList has two especially cheap operations:

• insert_front(data): create a Node and hook it in as the new head → O(1).
• Removing the head: move the head pointer to the next node → O(1).

Now ask yourself this question: what happens if you forbid yourself every other operation? No insert_at, no removing by predicate in the middle of the list, no walking the list to search. You may only touch one end: the head.

What you get is a more restricted structure... and precisely because of that, a conceptually more powerful one. By limiting the operations, the structure acquires a predictable behavior that models real situations: the stack.

This idea — gaining clarity by removing freedom — is a recurring theme in data structures. A stack is not "a list with things missing": it is a different contract, with its own guarantees, that just happens to be buildable on top of a list. Recall the ADT vs. implementation distinction from module 1: there we saw ListStack and DictStack as an example of one contract admitting several implementations. The time has come to understand that contract for real.

A stack is a collection where elements always enter and leave through the same end, called the top. The consequence is the rule that defines the stack:

LIFO: Last In, First Out — the last one in is the first one out.

Picture the stack of clean plates in a kitchen:

• When you wash a plate, you place it on top of the stack.
• When you need a plate, you take the one on top.
• The plate at the bottom may have been there for weeks: it will only come out once every plate above it has been removed.

Nobody pulls a plate out of the middle (everything would end up on the floor). That physical restriction is exactly the stack's logical restriction.

When you press Ctrl+Shift+T in your browser to reopen a closed tab, which one comes back? The last one you closed. Press it again, and the one before that reappears. The browser keeps closed tabs on a stack: every close "pushes" a tab, every reopen "pops" the most recent one.

There is an opposite policy, FIFO (First In, First Out, like the checkout line at the supermarket): that is the queue, the star of module 4. For now we only keep the contrast:

Like every ADT, the stack is defined by its operations, not by how they are implemented. This is the contract we will use throughout the module (and the exact names we will implement in lesson 03-03):

Notice three details of the contract:

• pop does two things at once: it removes and returns. There is no "remove without knowing what you removed".
• peek exists because pop is destructive. You often want to know what's on top (for instance, "what would the next action to undo be?") without undoing it yet.
• There is no access by position. You cannot ask "what's at position 3?". If you need that, you don't need a stack; you need a list.

In lesson 03-02 we will walk through each operation step by step, with traces of the stack's state; in 03-03 we will implement them in two different ways. Today it is enough to understand what they promise.

The following diagram shows the central idea: push and pop always operate on the same end, the top.

Reading the diagram:

• action_1 was the first to enter and ended up at the bottom: it will be the last to leave.
• action_3 is the current top: peek() would show it, pop() would remove it.
• If we now did push(action_4), it would become the new top, covering action_3.

Notice the parallel with the linked list: the stack's top will play the role of the list's head. That is why the promise in 02-05 was no exaggeration: you already have the whole mechanism down.

Stacks are no academic curiosity: you are using them right now, even if you can't see them.

Every time Python executes a function, it pushes a record with its local variables and the return point. When the function finishes, that record is popped and execution resumes where it left off. That's why, when a function a() calls b() and b() calls c(), we return to b() when c() finishes, and to a() when b() finishes: the last one in is the first one out. When you see an error traceback in Python, you are looking at a snapshot of that stack. We will explore it with code in lesson 03-04.

Every text editor keeps each change on a stack. Ctrl+Z pops the most recent change and reverts it. It is the flagship application of stacks and the one we will build for TaskFlow.

The browser's "back" button behaves like a stack of visited pages. In module 2 we already built TaskHistory on a doubly linked list to move back and forward; in lesson 03-04 we will see that "back and forward" can also be modeled with two cooperating stacks, and we will compare both approaches.

• Checking that parentheses and brackets are balanced (03-04).
• Evaluating mathematical expressions (03-04).
• Traversing trees and graphs depth-first (DFS): we will preview it in 03-04 and you will develop it in modules 6 and 7.

Let's place ourselves in TaskFlow. A user works with their tasks, represented as dictionaries:

Over the course of the morning, the user:

1. Creates task 7.
2. Changes its priority from 2 to 1.
3. Marks it as "in_progress".
4. Assigns it to Anna ("assigned_to": "anna").

Now they press Undo. What do they expect to happen? That the assignment to Anna is reverted — not that the task gets deleted. They press Undo again: the task goes back to "pending". Again: the priority goes back to 2.

In other words: undo reverts the actions in the reverse order they were performed. The last action taken is the first one undone. That is LIFO to the letter, and that is why the right structure for undo is a stack:

• Every time the user does something → push(action) onto the history stack.
• Every time they press Undo → pop() retrieves the most recent action and it gets reverted.
• Is the Undo button enabled? → is_empty() decides.
• "Undo: change priority" as the button's text → peek() without touching anything.

Notice that the interface's four real needs map one-to-one onto the ADT's contract. When that happens, you have chosen the right structure.

Part of the stack's contract is its performance. A well-implemented stack guarantees that all its operations run in constant time:

No operation depends on how many elements there are: whether TaskFlow's history holds 10 actions or 10 million, undoing the last one costs the same. Compare that with the list, where searching or inserting in the middle was O(n): by restricting the contract, we have been able to guarantee that everything the stack offers is O(1). In lesson 03-03 we will verify this table with timeit, and we will refine the difference between amortized O(1) and guaranteed O(1) depending on the implementation.

• Confusing a stack with a list: if you catch yourself wanting to access "the third element" of a stack, stop. Either you are using the wrong structure, or you are breaking the contract. The restricted contract is the stack's whole point, not a limitation to work around.
• Confusing LIFO with FIFO: a mnemonic trick: a stack of plates (the last one on top comes off first), a queue at the cinema (the first to arrive gets in first). If in doubt, draw three elements going in and ask yourself which one comes out.
• Thinking that peek modifies the stack: peek is read-only. If the stack changed after a peek, the implementation is wrong (we will watch for this in 03-03).
• Believing the stack "remembers positions": in a stack an element has no stable index; its only positional property is "how many elements sit above it", and that changes with every operation.
• Tip: when analyzing a problem, ask yourself: "is the last thing to arrive the first thing I need to process?". If the answer is yes, there is almost certainly a stack waiting for you.

Without implementing anything (pen and paper will do), start from an empty stack and apply this sequence. What does each pop() and peek() return, and what is left on the stack at the end?

For each situation, say whether the natural behavior is LIFO (a stack) or not, and justify it in one sentence:

1. The messages in a chat, displayed in the order they arrived.
2. The backspace key deleting characters from what you type.
3. The office printer processing documents sent by several people.
4. Exiting several nested menus in an application by pressing "back" repeatedly.

Write down (in pseudocode or plain sentences, no implementation) which operation of the stack contract you would use for each need of TaskFlow's interface:

1. Showing the "Undo" button grayed out when there is nothing to undo.
2. Showing the text of the next action to undo as the button's tooltip.
3. Recording that the user has just completed task 12.
4. Executing the undo when the user presses the button.
5. Showing "History: 8 actions" in the status bar.

Solution 1:

At the end only "create task 1" remains. Notice that peek changed nothing: the following pop returned the same element.

Solution 2:

1. Not a stack (it's FIFO): messages are shown in arrival order. It is a queue (module 4).
2. Stack: backspace deletes the last character typed; the text behaves like a stack of characters.
3. Not a stack (it's FIFO): it would be unfair for the last document sent to print first. A print queue, literally.
4. Stack: each opened menu is pushed; "back" pops the most recent one. It is the same pattern as the call stack.

Solution 3:

1. is_empty() → if it returns True, gray out the button.
2. peek() → reads the top without removing it; perfect for a tooltip.
3. push(action) → records the action of completing task 12.
4. pop() → retrieves the most recent action so it can be reverted.
5. size() → returns the number of stored actions.

In this lesson you have met the stack as an abstract data type: a LIFO collection where everything happens at the top, with a five-operation contract (push, pop, peek, is_empty, size) that promises O(1) cost for all of them. You have seen that this restriction is not a weakness but the key to its usefulness: it models exactly an editor's undo, the browser's closed tabs, Python's call stack and — our concern here — TaskFlow's undo, where every need of the interface matches one operation of the contract. You have also confirmed that the stack directly inherits what you learned in module 2: the top is the head of a linked list with the expensive operations forbidden. In the next lesson we will open the hood on each operation: we will walk through push, pop and peek step by step with traces of the stack's state, decide what to do when someone calls pop on an empty stack, and start practicing with TaskFlow's undo using Python's list as a provisional stack.