A data structure is a way of organising data so that particular operations are efficient. The choice of structure is often the single biggest factor in a program's speed. The fundamentals:

• Array — a contiguous block; access element i in O(1) by computing its address, but insertion in the middle costs O(n) because elements must shift.
• Linked list — nodes each holding a value and a pointer to the next; O(1) insertion once you hold the spot, but O(n) to find a position (no index arithmetic).
• Stack — Last-In-First-Out (LIFO); push and pop at one end. Models function calls, undo, backtracking.
• Queue — First-In-First-Out (FIFO); enqueue at the back, dequeue at the front. Models fairness, buffering, breadth-first search.
• Hash map — key→value store giving average O(1) lookup by hashing the key to a bucket.
• Tree — a hierarchy of nodes; a binary search tree keeps keys ordered for O(log n) search when balanced.

The recurring theme is trade-offs: no structure is best at everything. Arrays win at random access and lose at insertion; linked lists are the reverse. A hash map buys near-instant lookup at the cost of order and worst-case guarantees. Choosing a data structure is choosing which operations you want to be cheap, accepting that others become expensive.

The hash map deserves special respect: it turns "search a haystack" into "compute an address." A hash function scrambles a key into a bucket index; you go straight there. Collisions (two keys landing in one bucket) are handled by chaining or probing, and a good hash keeps them rare — which is why dictionaries feel instantaneous even with millions of entries.

We implement a stack and a queue from scratch, then use the stack to check whether brackets in an expression are balanced — a real parsing task.

class Stack:
    def __init__(self):
        self.items = []
    def push(self, x): self.items.append(x)        # add to top
    def pop(self):     return self.items.pop()     # remove from top (LIFO)
    def peek(self):    return self.items[-1]
    def is_empty(self): return len(self.items) == 0

def balanced(expr):
    """Return True if every bracket is correctly matched and nested."""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = Stack()
    for ch in expr:
        if ch in "([{":
            stack.push(ch)                         # opening -> remember it
        elif ch in ")]}":
            if stack.is_empty():
                return False                       # closing with nothing open
            if stack.pop() != pairs[ch]:
                return False                       # mismatched kind
    return stack.is_empty()                        # nothing left unclosed

print(balanced("a(b[c]{d})e"))     # True
print(balanced("(]"))              # False  (wrong kind)
print(balanced("(("))              # False  (unclosed)

# A queue: FIFO using two ends of a list
from collections import deque
q = deque()
q.append("first"); q.append("second")             # enqueue at back
print(q.popleft())                                 # dequeue front -> "first"

The bracket-matcher is why stacks matter: the "last opened, first closed" nesting of brackets is exactly LIFO. Compilers use this same idea to parse nested structure in every program you write.