Stack: LIFO and Typical Errors

A stack stores elements according to the LIFO principle: the last element added is the first one removed. Typical operations are push (place on top), pop (remove and return from top), and peek or top (read from top without removing).

Use cases: bracket checking, undo buffer, evaluation of postfix expressions, runtime stack during method calls.

Example trace: push(A), push(B), pop returns B, peek returns A.

Edge case: pop or peek on an empty stack results in underflow. The specification must define whether an exception is thrown or a special value is returned.

$$\operatorname{pop}(\operatorname{push}(S,x))=x$$

Where used

Call stack of the JVM, undo buffer in editors, expression evaluation, and DFS with explicit stack. In compilers and interpreters, LIFO is the standard for nested context switches. Empty pops without checks are a classic production error in parsers.

Depth

In a LIFO storage, only the last inserted element is directly accessible. This limitation is useful: nested structures, return points, and still open subproblems are processed in exactly reverse order of their creation.

A central invariant is that top always points to the next element to be removed or unambiguously encodes the empty state. Whether top points to the top occupied field or the first free field is an implementation decision that must be consistent in all operations.

An overflow relates to fixed capacity, while an underflow refers to accessing an empty memory. Library implementations typically grow dynamically but can still fail due to memory limits. Applications should not confuse empty states with a regular return value.

Difficulty levels

1. Simulate a sequence of insert and remove operations.
2. Specify the top invariant for two index conventions.
3. Justify a parser or iterative depth search using this principle.

Pitfalls

Checks and removals are often separated, even though the state can change in between. Additionally, an inconsistently interpreted top index can lead to off-by-one errors.