Приведи пример структуры данных

Примеры структур данных в Python

Структура данных — это способ организации информации для эффективного доступа и модификации. Разберём практические примеры.

1. Stack (Стек) — LIFO (Last In First Out)

Когда использовать: undo/redo, парсинг скобок, DFS, browser history.

# Реализация с list (Python list = динамический array)
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def peek(self):
        return self.items[-1] if not self.is_empty() else None

# Пример: Undo/Redo
class TextEditor:
    def __init__(self):
        self.undo_stack = Stack()
        self.redo_stack = Stack()
        self.content = ""
    
    def type_text(self, text):
        self.undo_stack.push(self.content)
        self.content += text
        self.redo_stack = Stack()  # Очищаем redo при новом действии
    
    def undo(self):
        if not self.undo_stack.is_empty():
            self.redo_stack.push(self.content)
            self.content = self.undo_stack.pop()
    
    def redo(self):
        if not self.redo_stack.is_empty():
            self.undo_stack.push(self.content)
            self.content = self.redo_stack.pop()

# Пример: Проверка сбалансированных скобок
def is_balanced(expression):
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:
            stack.push(char)
        elif char in pairs.values():
            if stack.is_empty() or pairs[stack.pop()] != char:
                return False
    
    return stack.is_empty()

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

2. Queue (Очередь) — FIFO (First In First Out)

Когда использовать: BFS, task scheduling, печать очередь, обработка событий.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Пример: BFS (поиск в ширину)
def bfs(graph, start):
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    
    while not queue.is_empty():
        node = queue.dequeue()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.enqueue(neighbor)
                visited.add(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}

bfs(graph, 'A')  # A B C D E

3. Linked List (Связный список)

Когда использовать: Динамическое добавление/удаление, когда размер неизвестен, когда нет локальности памяти.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def delete(self, data):
        if not self.head:
            return
        
        if self.head.data == data:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(' -> '.join(elements))

# Использование
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_beginning(0)
ll.display()  # 0 -> 1 -> 2 -> 3

4. Hash Table / Dictionary (Хэш-таблица)

Когда использовать: Быстрый поиск по ключу, кэширование, подсчёт частоты.

# Python dict уже это есть, но вот реализация

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def set(self, key, value):
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                return

# Пример: Подсчёт частоты слов
def count_words(text):
    words = text.lower().split()
    word_count = {}
    
    for word in words:
        word_count[word] = word_count.get(word, 0) + 1
    
    return word_count

counts = count_words("hello world hello python hello")
print(counts)  # {'hello': 3, 'world': 1, 'python': 1}

5. Tree (Дерево) — особенно Binary Search Tree (BST)

Когда использовать: Иерархические данные, поиск, сортировка, файловая система.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value):
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if node is None:
            return False
        
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def inorder_traversal(self):
        result = []
        self._inorder(self.root, result)
        return result
    
    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)

# Использование
bst = BinarySearchTree()
for val in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(val)

print(bst.inorder_traversal())  # [20, 30, 40, 50, 60, 70, 80] (sorted)
print(bst.search(40))  # True
print(bst.search(25))  # False

6. Heap (Куча)

Когда использовать: Priority queue, Dijkstra, heap sort.

import heapq

# Min Heap (Python heapq)
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)
heapq.heappush(min_heap, 1)

print(heapq.heappop(min_heap))  # 1 (smallest)
print(heapq.heappop(min_heap))  # 3
print(heapq.heappop(min_heap))  # 5

# Max Heap (инверт значения)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)

print(-heapq.heappop(max_heap))  # 7 (largest)

# Пример: Priority Queue
class Task:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority
    
    def __lt__(self, other):
        return self.priority < other.priority

pq = []
heapq.heappush(pq, Task("high", 1))
heapq.heappush(pq, Task("low", 10))
heapq.heappush(pq, Task("medium", 5))

while pq:
    task = heapq.heappop(pq)
    print(f"{task.name} (priority {task.priority})")
# Output: high, medium, low

7. Graph (Граф)

Когда использовать: Соцсети, маршруты, рекомендации.

class Graph:
    def __init__(self):
        self.adjacency_list = {}
    
    def add_edge(self, u, v):
        if u not in self.adjacency_list:
            self.adjacency_list[u] = []
        self.adjacency_list[u].append(v)
    
    def dfs(self, start):
        visited = set()
        result = []
        
        def _dfs(node):
            visited.add(node)
            result.append(node)
            
            for neighbor in self.adjacency_list.get(node, []):
                if neighbor not in visited:
                    _dfs(neighbor)
        
        _dfs(start)
        return result

# Соцсеть
graph = Graph()
graph.add_edge('Alice', 'Bob')
graph.add_edge('Alice', 'Charlie')
graph.add_edge('Bob', 'David')
graph.add_edge('Charlie', 'David')

print(graph.dfs('Alice'))  # ['Alice', 'Bob', 'David', 'Charlie']

8. Trie (префиксное дерево)

Когда использовать: Автодополнение, словари, проверка орфографии.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        results = []
        self._dfs(node, prefix, results)
        return results
    
    def _dfs(self, node, prefix, results):
        if node.is_end:
            results.append(prefix)
        
        for char, child in node.children.items():
            self._dfs(child, prefix + char, results)

# Автодополнение
trie = Trie()
for word in ['apple', 'app', 'application', 'apply', 'apricot']:
    trie.insert(word)

print(trie.autocomplete('app'))  # ['app', 'apple', 'application', 'apply']

Когда какую использовать?

(m = длина слова, n = количество элементов)