Stacks

A stack exposes last-in, first-out access. Its core operations are push(x), pop(), peek() or top(), isEmpty(), and usually size(). With a dynamic array, append and remove the final element, tracking no extra pointer beyond the array length; this has amortized O(1) push because occasional resizing copies the buffer. With a linked list, keep the head as top so push and pop are worst-case O(1), at the cost of node allocation and poorer locality. Define underflow deliberately: throw, return an option, or return a documented sentinel, but never read a nonexistent top. Capacity is another explicit contract for a fixed array implementation. Demonstrate LIFO with balanced parentheses, undo history, DFS, or evaluating postfix expressions. Edge cases include popping an empty stack, one remaining item, repeated equal values, and clearing state. All normal operations are O(1), while storage is O(n).