Picture a pile of dishes: you add a dish to the top, and the top dish is the first one you take away. A stack is a container with that same last-in, first-out (LIFO) rule. It is useful when the most recent item should be handled first—not when people are waiting their turn. section 8.2 section 1.10
The interface keeps access deliberately narrow:
- Push adds an element to the top. section 8.19
- Pop removes and returns the top element. section 8.19
- Peek, when provided, reads the top element without removing it. Inserting or deleting elsewhere—and generally searching—is not part of the stack interface. section 8.19
The interface says what a stack does; its underlying data structure determines how it stores elements. One Python implementation makes Stack a wrapper around a singly linked list. The list’s front serves as the top: insertion and deletion there each take O(1) time in the worst case, and the stack need not traverse the list. section 8.5 section 8.8 section 8.9
class Stack:
def __init__(self):
self._data = SinglyLinkedList()
The class constructor creates an empty SinglyLinkedList; the wrapper exposes only the operations appropriate to a stack. section 8.9
A linked list lets the stack grow and shrink, but each node needs space for a link. A static array may be preferable when the required size is known. With a dynamic array, push and pop have O(1) amortized time but can take O(n) in the worst case; profiling can help compare implementations in a particular language. section 8.8 section 8.19
Evaluate a postfix expression
In `3 2 4 * +`, push each number as it appears. At `*`, pop the last two numbers, multiply them, and push the result. At `+`, do the same for addition. The stack makes the most recently encountered operands available to the next operator. section 8.16
Undo and retrace
An editor can keep changes on an undo stack and move undone changes to a redo stack. A game can push rooms as a player enters them, then pop rooms to retrace the path. Both tasks need the latest step first. section 8.17 section 8.18
Take care with peek in a linked-list wrapper. Reading the list’s private head directly fails on an empty stack and may hand callers a reference to a mutable object. Check for emptiness and provide a suitable linked-list access method rather than reaching into its private attribute. section 8.12
