liveBook · Manning

First-in-last-out structure

As explained in Algorithms Every Programmer Should Know

LIFO is an ordering rule in which the most recently added element is the first one removed.

LIFO means the most recently added element is the first one removed. A stack follows this rule: add 3, 4, 6, then 8, and 8 comes off first. Think of a stack of pancakes—you take the one on top. section 1.4.3

Calls and backtracking

A function call pushes its local variables and parameters; when it finishes, it pops off and control returns to the caller. Depth-first search uses the same pattern to backtrack from a dead end. section 1.4.3 section 1.4.4

Figure 1.6 The stack data structure is Last In First Out(LIFO). Illustration of a stack with three numbers. The number 8 was inserted last and it will be popped first. The number 4 was inserted first, it will be popped only when all the numbers above the stack are popped first.

The stack illustration shows why the last inserted number, 8, is popped before the earlier numbers. section 1.4.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines LIFO, traces a four-number example, names stack operations and gives their time and space complexity.
Examples
Uses a pancake stack, inserting 3, 4, 6, and 8, function calls, undo and redo, and depth-first search backtracking.
What you can do after
Apply LIFO with a stack to support depth-first search, function calls, recursion, and undo or redo operations.
How it connects
Connects stacks with recursion, function calls, undo and redo, and depth-first search; contrasts them with queues and breadth-first search.

Also explained in

Compare how 3 books explain first-in-last-out structure →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.