Stack

A stack models last-in, first-out state: the most recently opened bracket, unresolved operation, or candidate element is the next one that must be handled. Use push to add, pop to remove the top, and peek to inspect it. In many languages a dynamic array gives amortized O(1) push and O(1) pop at the end; a linked implementation gives worst-case O(1) operations but adds allocation overhead. The real interview question is the stack invariant. For balanced parentheses, it contains unmatched opening delimiters; for monotonic-stack tasks, it contains candidates in a specified increasing or decreasing order. Never pop without checking emptiness, and do not use a queue when order must reverse. A stack holds at most n input items, so typical extra space is O(n).