Stack: What Does "Last-In-First-Out" Mean? Principle Diagram

Imagine the plate you use every morning. After washing, the plates are stacked together. The top plate is the one you just placed. To take a plate, you must first take the top one, right? This process of “the earlier placed plate is at the bottom, the later placed is on top, and the top one is taken first” is actually the core feature of the data structure we’re going to discuss today—the stack.

一、What is a Stack?¶

A stack is a special type of linear list. Its uniqueness lies in: it only allows insertion and deletion operations from one end. We call this end the “top” of the stack, and the other end the “bottom” of the stack. Just like stacking plates, the bottom of the stack is the lowest plate, and the top is the highest plate; you can only place (push) or take (pop) plates from the top, not from the bottom.

二、Core Feature: Last In First Out (LIFO)¶

The most critical feature of a stack is “Last In First Out” (LIFO). This means: The element that was last pushed onto the stack will be the first to be popped out.

For example:
- When you load bullets into a magazine, the last bullet you insert is on top. When firing, you first shoot the top bullet (the last inserted), which is LIFO.
- Making the bed: the bed made on Monday is at the bottom, and the one made on Tuesday is on top. When tidying, you first take the Tuesday bed (the later one), which is also LIFO.

Compare it with a queue (First In First Out, FIFO): When queuing to buy tickets, the first person gets the ticket first (FIFO). A stack is like “cutting the queue”—the last person who cuts gets processed first.

三、Basic Operations of a Stack¶

A stack has only two core operations: push (insert) and pop (delete). Additionally, it supports viewing the top element (top) and checking if it is empty (empty).

• Push: Add an element to the top of the stack.
  Example: You place a new plate on the stack, and it becomes the new top.
• Pop: Remove an element from the top of the stack and return it.
  Example: You take the top plate from the stack; after removal, the new top is the next plate.
• Top: View the top element without removing it (e.g., checking the appearance of the top plate).
• Empty: Check if the stack is empty (e.g., confirming if the plate stack is empty).

四、Stack Principle Diagram (Understanding with Examples)¶

Let’s execute the following operations in order, marking push order with numbers and pop order with arrows:

1. Initial State: The stack is empty (represented by [], where the left side is the bottom and the right side is the top).
   Stack: []

2. Push 1: Add 1 to the top.
   Stack: [1]

3. Push 2: Add 2 to the top.
   Stack: [1, 2]

4. Push 3: Add 3 to the top.
   Stack: [1, 2, 3]

5. Pop: Remove the top element (3). The new top is 2.
   Stack: [1, 2]
   (Popped element: 3)

6. Pop: Remove the top element (2). The new top is 1.
   Stack: [1]
   (Popped element: 2)

7. Pop: Remove the top element (1). The stack is empty.
   Stack: []
   (Popped element: 1)

五、Practical Application Scenarios of Stacks¶

Stacks are ubiquitous in programming and daily life. Here are classic examples:

1. Parenthesis Matching: Verify if an expression like (a + b) * (c - d) is valid. Use a stack to record left parentheses; when encountering a right parenthesis, pop the top left parenthesis. If the stack is empty at the end, the parentheses are balanced.
2. Function Call Stack: When a program calls main, which calls func1, which calls func2, func2 returns to func1, then func1 returns to main. This follows the LIFO rule (the last called function returns first).
3. Browser Back Button: If you open pages 1→2→3, the back button navigates back to 2→1, equivalent to popping the top elements (3→2→1).
4. Expression Evaluation: For calculations like 3 + 4 * 2 / (1 - 5), the stack manages operator precedence: process parentheses first, then multiplication/division, and finally addition/subtraction.

六、Summary¶

A stack is a “Last In First Out” linear structure, only allowing operations on the top. Its core is “LIFO”. It plays a key role in parentheses matching, function calls, and browser back functionality. Remember: A stack is like stacking plates—later placed plates are taken first, and earlier placed ones are taken later.

After understanding its basic operations and features, you’ll find stacks are powerful tools for solving problems. For example, stacks are frequently used in recursion and dynamic programming later.

(PS: If abstract, simulate with a pen holder: Insert pens from bottom to top, and take the top pen each time—that’s the “LIFO” of a stack!)