A stack is a container that removes elements in the inverse order of insertion: the most recently added element is returned first. A pile of files or dishes provides the intuition: work comes off the top before older items below it. section 1.1.1
Treat a stack as an abstract data type with two central operations:
- Insert an element into the container. section 1.1.1
- Remove an element; when the stack is nonempty, removal returns the most recently inserted element. section 1.1.1
- Choose a representation—such as an array, linked list, or another storage system—while preserving the same abstract behavior. section 1.1.1
Depth-first graph traversal
Depth-first search uses a stack, either explicitly or implicitly through recursion. Newly discovered vertices enter the container, and the next vertex taken is the one that lets traversal continue as far as possible before backtracking. section 14.3.5
Figure 1.1 The (simplified) internal representation of an array. Each element of the array in the picture corresponds to a byte of memory,2 whose address is shown below it. Each element’s index is shown above it. An array is stored as a contiguous block of memory, and each element’s address can be obtained by adding its index within the array to the offset of the first element. For instance, the fourth character of the array (array[3], empty in the figure), has address 0xFF00 + 3 = 0xFF03.
An array can serve as a concrete storage choice, but its contiguous memory layout and indexing details belong to the implementation rather than the stack’s abstract definition. section 1.1.1
