Data Structures: Lists, Stacks and Queues
What this domain tests
Lists, stacks and queues tests linear data structures, their operations, LIFO/FIFO behaviour and applications. Expect output prediction, pointer/front-rear tracking and complexity.
Core rules
- A list stores elements in sequence with index access; Python lists are dynamic arrays, so append is amortised O(1), while insertion/deletion in the middle is O(n).
- A stack is LIFO: push adds at the top, pop removes from the top, peek reads the top. Operations are O(1) in a list/array implementation. Applications: function calls, undo, expression evaluation, backtracking.
- A queue is FIFO: enqueue at the rear, dequeue from the front. A simple list dequeue is O(n); a circular queue reuses space with front and rear indices.
- Overflow means no space; underflow means deleting from an empty structure.
Worked example
Stack: push 10, push 20, push 30; pop returns 30; peek returns 20; pop returns 20. Remaining stack: [10]. Queue: enqueue 1, 2, 3; dequeue returns 1; front is 2; rear is 3. Reasoning: a stack removes the most recently added item; a queue removes the earliest.
Traps
Do not confuse top with the bottom element. In a circular queue, (rear + 1) % size == front often signals full, so one slot may be sacrificed. Do not say a Python list pop() removes the first item; it removes the last by default. Underflow is not a syntax error. Do not assume a stack is FIFO because a list can append and remove at either end.