Data Structures · topic
Stack operations and their costs in array and linked implementations, two stacks in one array, balanced brackets, recursion and the call stack, valid pop sequences and Catalan counts, and infix, prefix and postfix conversion and evaluation with full stack traces.
The stack abstract data type and its constant-time operations, array and linked implementations with their overflow and underflow tests, two stacks sharing one array, balanced-bracket checking with traces, recursion and the call stack (frames and call counts), and valid pop sequences: the Catalan count, the greedy check and the forbidden 3-1-2 pattern. Counts are verified by brute force over all permutations.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
Operator precedence and associativity, the operator-stack algorithm from infix to postfix with a full token-by-token trace, prefix by expression tree or by the reverse method, postfix evaluation traced by a compiled C program, prefix evaluation from right to left, the rank rule for valid postfix strings and postfix back to infix. Every conversion and value is computed by a verification script.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
