# CS 4991 - Week 2 ### Data Structures in Practice

# This Week - Focus: Recognizing problem patterns for common data structures.

# This Week - Focus: Recognizing problem patterns for common data structures. - Stacks (LIFO)

# This Week - Focus: Recognizing problem patterns for common data structures. - Stacks (LIFO) - Queues (FIFO)

# This Week - Focus: Recognizing problem patterns for common data structures. - Stacks (LIFO) - Queues (FIFO) - Dictionaries & Sets

# This Week - Focus: Recognizing problem patterns for common data structures. - Stacks (LIFO) - Queues (FIFO) - Dictionaries & Sets - `collections.deque`

## Stacks (LIFO) - Last-In, First-Out - Think of a stack of plates. - Operations: `push` (append), `pop`.

## Stacks (LIFO) - Archetypal Problems: - Balanced Parentheses - Expression Evaluation (e.g., Postfix/Reverse Polish Notation) - Backtracking (e.g., maze solving, implicit in recursion) - Practice: <https://open.kattis.com/problems/backspace>

## Queues (FIFO) - First-In, First-Out - Think of a line at a grocery store. - Operations: `enqueue` (append), `dequeue` (pop from front).

## Queues (FIFO) - Archetypal Problems: - Simulations - Level-order traversal in trees/graphs (Breadth-First Search) - Shortest path in unweighted graphs - Practice: <https://open.kattis.com/problems/guessthedatastructure>

## Performance Try this with a `list` first: <https://open.kattis.com/problems/integerlists>

## Python's `collections.deque` - "Double-ended queue" - The go-to for efficient stacks and queues in Python. - `append()` for stack push / queue enqueue. - `pop()` for stack pop. - `popleft()` for queue dequeue. - All operations are `$\mathcal{O}(1)$`.

## Dictionaries & Sets - Associative containers (hash maps/tables). - Keys mapped to values (`dict`) or just keys (`set`).

## Dictionaries & Sets - The default for: - Counting / Frequency Analysis - Tracking uniqueness / seen items - Average `$\mathcal{O}(1)$` for insertion, deletion, and lookup. - Worst case `$\mathcal{O}(N)$` (rare with good hash functions). - Practice: <https://open.kattis.com/problems/baconeggsandspam>