An ADT defines what operations a data structure supports — not how it is implemented.

Layer	Concern
Interface	Operations and their behavior
Implementation	How operations are carried out

The interface is the contract. Users of an ADT only need to know the interface.

# Interface — what a Stack does:
# push(item)     add to top
# pop()          remove from top
# peek()         view top without removing
# is_empty()     True if no items

# Implementation A — using a Python list
class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)

    def pop(self):
        return self._data.pop()

    def peek(self):
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

Last In, First Out — like a stack of plates.

Use cases:

• Function call stack
• Undo/redo history
• Balanced parentheses checking
• Depth-first search

stack = []
stack.append("a")   # push
stack.append("b")
stack.append("c")
print(stack.pop())  # c  (last in, first out)
print(stack.pop())  # b

Balanced parentheses

def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False

First In, First Out — like a line at a checkout.

Use cases:

• Task scheduling
• BFS graph traversal
• Print queues
• Message queues

from collections import deque

queue = deque()
queue.append("task1")     # enqueue
queue.append("task2")
queue.append("task3")

print(queue.popleft())    # task1  (FIFO)
print(queue.popleft())    # task2

# deque is O(1) at both ends
# list.pop(0) is O(n) — avoid for queues

Key terms:

• Root — top node (no parent)
• Leaf — node with no children
• Height — longest root-to-leaf path
• BST — Binary Search Tree: left < node < right

Traversals:

• Pre-order: root → left → right
• In-order: left → root → right (sorted for BST)
• Post-order: left → right → root

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.val, end=" ")
    inorder(node.right)

# Build a small BST:  4
#                    / \
#                   2   6
root = Node(4)
root.left = Node(2)
root.right = Node(6)
inorder(root)   # 2 4 6

Vertices (nodes) connected by edges.

• Directed — edges have direction
• Undirected — edges go both ways

Representation:

# Adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(graph, "A")   # A B C D