Data Structures: Lists, Stacks and Queues
What this domain tests
Linear data structures: how lists store elements in contiguous memory, and how stacks and queues restrict access to solve specific problems. Questions cover insertion and deletion in arrays, LIFO and FIFO behaviour, overflow and underflow, and applications such as expression evaluation, function calls, job scheduling and printer spooling.
Core rules
- Array list: elements are indexed from 0; direct access is O(1), but insertion or deletion in the middle shifts elements, O(n). A static array's size is fixed at declaration.
- Stack: push adds at the top, pop removes from the top; both O(1). The top pointer starts at −1. Push on a full stack is overflow; pop on an empty stack is underflow.
- Queue: enqueue at the rear, dequeue at the front. A linear queue leaves unusable space after dequeues, so a circular queue is used.
- Stack applications: reversal, balanced parentheses, postfix evaluation, recursion and backtracking. Queue applications: CPU scheduling, buffering and breadth-first search.
Worked example
Evaluate postfix 5 3 + 8 2 − *. Read left to right and push operands. Push 5, push 3. The + pops 3 and 5, computes 8, and pushes 8. Push 8, push 2. The − pops 2 and 8, computes 8−2=6, and pushes 6. The * pops 6 and 8 and computes 48. The result is 48.
Traps that cost marks
Reversing operand order in subtraction or division during postfix evaluation; popping from the rear of a queue; forgetting to test underflow before pop; assuming a stack can be searched by index; confusing rear and front in enqueue; describing a queue as LIFO.