One idea
Stacks and queues are about order. Linked lists are about cheap pointer changes when you already have the node.
If you need random access by index, do not pick a linked list. Use an array or list instead.
When to use stack
Use a stack when the last item seen must be handled first. Think undo, browser back, valid brackets, next greater element, monotonic stack problems, DFS without recursion.
In most languages, use the built-in dynamic array as a stack. In Python, list append and pop at the end are fine.
When to use queue
Use a queue when the first item waiting must be handled first. Think ticket counters, BFS, level order traversal, task scheduling, and sliding windows.
In Python, do not use list.pop(0). It shifts items. Use collections.deque for O(1) append and popleft.
Linked list trap
A linked list is not automatically better because interviews mention it often. Traversing to the middle is O(n), and it uses extra pointers.
Use it when the problem is about node links: reverse a list, detect a cycle, merge two sorted lists, remove a node, or use slow and fast pointers.
Stack example
Put this in your repo as code/python/valid_parentheses.py. It shows the real stack pattern and has no extra classes.
def is_valid(s: str) -> bool:
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs.values():
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
return False
return len(stack) == 0
def test_is_valid():
assert is_valid("()[]{}") is True
assert is_valid("([{}])") is True
assert is_valid("(]") is False
assert is_valid("((") is FalseQueue example
For queues, prefer deque in Python. This small BFS shape will repeat later when you reach trees and graphs.
from collections import deque
def time_to_process(tasks):
q = deque(tasks)
order = []
while q:
order.append(q.popleft())
return order
def test_time_to_process():
assert time_to_process(["A", "B", "C"]) == ["A", "B", "C"]Write comparison notes
Your kit should not just dump solutions. Add short notes that explain why this structure fits.
A good note says: access pattern, main operations, costs, and why you rejected another option.
# notes/stacks-queues-linked-lists.md
Problem: Valid parentheses
Pick: Stack
Why: Need to match the latest unmatched opening bracket first.
Cost: O(n) time, O(n) space in the worst case.
Rejected: Queue, because oldest bracket first does not match nesting.
Problem: Process tasks in arrival order
Pick: Queue using deque
Why: First task should be processed first.
Cost: O(n) time, O(n) space.
Rejected: Python list with pop(0), because removing from the front shifts items.
Problem: Detect linked list cycle
Pick: Slow and fast pointers
Why: We only move through next links. No index access is needed.
Cost: O(n) time, O(1) space.
Rejected: Array copy, because it uses extra space and changes the problem shape.Do this now
Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.
0 of 5 done