Дата-структуры: Stack, Queue, Heap, Array, Baum, Graph и алгоритмы

Этот материал дает полный обзор ключевых дата-структур — с анализом сложности, практическими примерами и алгоритмами.

Краткая суть

Дата-структуры — это способы организации и хранения данных так, чтобы к ним можно было эффективно обращаться и их можно было изменять. Выбор правильной структуры решающим образом влияет на производительность.

Определение

Дата-структуры — это фундаментальные блоки разработки программного обеспечения, которые определяют организацию и управление данными. Каждая структура имеет свои характеристики и области применения.

Основные дата-структуры:

1. Array

• Описание: фиксированная, непрерывная последовательность элементов одного типа
• Доступ: прямой по индексу (O(1))
• Недостатки: фиксированный размер, вставка и удаление требуют O(n) операций

2. Stack (LIFO)

• Принцип: Last-In, First-Out
• Операции: push() (добавить в начало), pop() (удалить из начала)
• Применение: вызовы функций, backtracking, парсеры

3. Queue (FIFO)

• Принцип: First-In, First-Out
• Операции: enqueue() (добавить в конец), dequeue() (удалить из начала)
• Применение: очереди печати, поиск в ширину (BFS)

4. Heap

• Описание: бинарное дерево со свойством кучи
• Виды: Min-Heap, Max-Heap
• Применение: приоритетные очереди, сортировка кучей

5. Дерево

• Описание: иерархическая дата-структура
• Виды: бинарное дерево, BST, AVL, B-дерево
• Применение: алгоритмы поиска, базы данных

6. Граф

• Описание: вершины и ребра
• Виды: направленный/ненаправленный, взвешенный/невзвешенный
• Применение: сети, планирование маршрутов

Ключевые моменты

• Array: прямой доступ O(1), фиксированный размер
• Stack: LIFO, операции push/pop
• Queue: FIFO, операции enqueue/dequeue
• Heap: Min/Max-Heap, приоритетная очередь
• Дерево: иерархическая структура, BST, балансировка
• Граф: структура вершины-ребра, алгоритмы обхода
• Big-O нотация: анализ временной и пространственной сложности
• Важно для exam: ключевой материал для алгоритмов и эффективности

Основные компоненты

1. Array: индексированная коллекция с фиксированным размером
2. Stack: LIFO структура с операциями push/pop
3. Queue: FIFO структура с операциями enqueue/dequeue
4. Heap: приоритетная структура на основе дерева
5. Дерево: иерархические отношения родитель-потомок
6. Граф: сеть из вершин и ребер
7. Сложность: Big-O анализ операций
8. Алгоритмы: поиск, сортировка, обход структур

Практические примеры

1. Array и ArrayList в Java

import java.util.*;

public class ArrayDemo {
    public static void main(String[] args) {
        // Простой массив (фиксированный размер)
        int[] zahlen = new int[5];
        zahlen[0] = 10;
        zahlen[1] = 20;
        zahlen[2] = 30;
        zahlen[3] = 40;
        zahlen[4] = 50;
        
        // Прямой доступ O(1)
        System.out.println("Element bei Index 2: " + zahlen[2]);
        
        // Линейный поиск O(n)
        int gesucht = 30;
        int index = -1;
        for (int i = 0; i < zahlen.length; i++) {
            if (zahlen[i] == gesucht) {
                index = i;
                break;
            }
        }
        System.out.println("Index von " + gesucht + ": " + index);
        
        // ArrayList (динамический размер)
        List<String> namen = new ArrayList<>();
        namen.add("Alice");  // O(1) амортизировано
        namen.add("Bob");    // O(1) амортизировано
        namen.add("Charlie"); // O(1) амортизировано
        
        // Вставка в середину O(n)
        namen.add(1, "David"); // Все элементы сдвигаются вправо
        
        System.out.println("ArrayList: " + namen);
        
        // Сравнение производительности Array и ArrayList
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 100000;
        
        // Производительность Array
        long start = System.nanoTime();
        int[] array = new int[GROESSE];
        for (int i = 0; i < GROESSE; i++) {
            array[i] = i;
        }
        long arrayZeit = System.nanoTime() - start;
        
        // Производительность ArrayList
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            arrayList.add(i);
        }
        long arrayListZeit = System.nanoTime() - start;
        
        System.out.println("Array Zeit: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList Zeit: " + arrayListZeit / 1_000_000 + " ms");
    }
}

2. Реализация Stack и его использование

import java.util.*;

// Реализация Stack с массивом
class ArrayStack<T> {
    private Object[] elemente;
    private int top;
    private final int kapazitaet;
    
    public ArrayStack(int kapazitaet) {
        this.kapazitaet = kapazitaet;
        this.elemente = new Object[kapazitaet];
        this.top = -1;
    }
    
    public void push(T element) {
        if (isFull()) {
            throw new StackOverflowError("Stack ist voll");
        }
        elemente[++top] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elemente[top--];
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elemente[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public boolean isFull() {
        return top == kapazitaet - 1;
    }
    
    public int size() {
        return top + 1;
    }
}

// Использование Stack
public class StackDemo {
    public static void main(String[] args) {
        // Встроенный Stack класс в Java
        Stack<String> stack = new Stack<>();
        
        // Операции push
        stack.push("Erstes");
        stack.push("Zweites");
        stack.push("Drittes");
        
        System.out.println("Stack: " + stack);
        System.out.println("Top Element: " + stack.peek());
        
        // Операции pop
        while (!stack.isEmpty()) {
            String element = stack.pop();
            System.out.println("Pop: " + element);
        }
        
        // Использование пользовательского Stack
        ArrayStack<Integer> meinStack = new ArrayStack<>(5);
        meinStack.push(10);
        meinStack.push(20);
        meinStack.push(30);
        
        System.out.println("\nCustom Stack:");
        while (!meinStack.isEmpty()) {
            System.out.println("Pop: " + meinStack.pop());
        }
        
        // Практическое применение: проверка скобок
        String ausdruck = "{[()]}";
        System.out.println("Ausdruck '" + ausdruck + "' ist gültig: " + 
                          pruefeKlammer(ausdruck));
    }
    
    // Проверка скобок со Stack
    public static boolean pruefeKlammer(String ausdruck) {
        Stack<Character> stack = new Stack<>();
        
        for (char zeichen : ausdruck.toCharArray()) {
            switch (zeichen) {
                case '(':
                case '[':
                case '{':
                    stack.push(zeichen);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
            }
        }
        
        return stack.isEmpty();
    }
}

3. Реализация очереди и её применение

import java.util.*;

// Реализация очереди на массиве (циклическая очередь)
class ArrayQueue<T> {
    private Object[] elemente;
    private int front, rear, size, kapazitaet;
    
    public ArrayQueue(int kapazitaet) {
        this.kapazitaet = kapazitaet;
        this.elemente = new Object[kapazitaet];
        this.front = this.size = 0;
        this.rear = kapazitaet - 1;
    }
    
    public void enqueue(T element) {
        if (isFull()) {
            throw new IllegalStateException("Queue ist voll");
        }
        rear = (rear + 1) % kapazitaet;
        elemente[rear] = element;
        size++;
    }
    
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue ist leer");
        }
        T element = (T) elemente[front];
        front = (front + 1) % kapazitaet;
        size--;
        return element;
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue ist leer");
        }
        return (T) elemente[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == kapazitaet;
    }
    
    public int size() {
        return size;
    }
}

// Применение очереди
public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue Interface с LinkedList
        Queue<String> queue = new LinkedList<>();
        
        // Добавление элементов
        queue.add("Kunde 1");
        queue.add("Kunde 2");
        queue.add("Kunde 3");
        
        System.out.println("Queue: " + queue);
        
        // Извлечение элементов
        while (!queue.isEmpty()) {
            String kunde = queue.remove();
            System.out.println("Bedient: " + kunde);
        }
        
        // Приоритетная очередь
        PriorityQueue<Integer> pqueue = new PriorityQueue<>();
        pqueue.add(30);
        pqueue.add(10);
        pqueue.add(20);
        pqueue.add(40);
        
        System.out.println("\nPriority Queue (natürliche Ordnung):");
        while (!pqueue.isEmpty()) {
            System.out.println("Element: " + pqueue.remove());
        }
        
        // Пользовательская очередь
        ArrayQueue<String> warteschlange = new ArrayQueue<>(3);
        warteschlange.enqueue("Aufgabe A");
        warteschlange.enqueue("Aufgabe B");
        warteschlange.enqueue("Aufgabe C");
        
        System.out.println("\nCustom Queue:");
        while (!warteschlange.isEmpty()) {
            System.out.println("Verarbeite: " + warteschlange.dequeue());
        }
    }
}

4. Куча и приоритетная очередь

import java.util.*;

// Реализация Min-Heap
class MinHeap {
    private List<Integer> heap;
    
    public MinHeap() {
        this.heap = new ArrayList<>();
    }
    
    public void insert(int wert) {
        heap.add(wert);
        heapifyUp(heap.size() - 1);
    }
    
    public int extractMin() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException("Heap ist leer");
        }
        
        int min = heap.get(0);
        int letzter = heap.remove(heap.size() - 1);
        
        if (!heap.isEmpty()) {
            heap.set(0, letzter);
            heapifyDown(0);
        }
        
        return min;
    }
    
    public int peek() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException("Heap ist leer");
        }
        return heap.get(0);
    }
    
    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap.get(parent) <= heap.get(index)) break;
            
            // Vertauschen
            Collections.swap(heap, parent, index);
            index = parent;
        }
    }
    
    private void heapifyDown(int index) {
        int groesse = heap.size();
        
        while (true) {
            int linkerKind = 2 * index + 1;
            int rechterKind = 2 * index + 2;
            int kleinster = index;
            
            if (linkerKind < groesse && heap.get(linkerKind) < heap.get(kleinster)) {
                kleinster = linkerKind;
            }
            
            if (rechterKind < groesse && heap.get(rechterKind) < heap.get(kleinster)) {
                kleinster = rechterKind;
            }
            
            if (kleinster == index) break;
            
            Collections.swap(heap, index, kleinster);
            index = kleinster;
        }
    }
    
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public int size() {
        return heap.size();
    }
}

// Применение Heap
public class HeapDemo {
    public static void main(String[] args) {
        // Java Priority Queue (Min-Heap)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(40);
        
        System.out.println("Min-Heap mit Priority Queue:");
        while (!minHeap.isEmpty()) {
            System.out.println("Min: " + minHeap.remove());
        }
        
        // Max-Heap с Comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(40);
        
        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println("Max: " + maxHeap.remove());
        }
        
        // Пользовательский Min-Heap
        MinHeap meinHeap = new MinHeap();
        meinHeap.insert(30);
        meinHeap.insert(10);
        meinHeap.insert(20);
        meinHeap.insert(40);
        
        System.out.println("\nCustom Min-Heap:");
        while (!meinHeap.isEmpty()) {
            System.out.println("Min: " + meinHeap.extractMin());
        }
        
        // Демонстрация сортировки через кучу
        heapSortDemo();
    }
    
    private static void heapSortDemo() {
        int[] zahlen = {12, 11, 13, 5, 6, 7};
        
        System.out.println("\nHeap Sort:");
        System.out.println("Original: " + Arrays.toString(zahlen));
        
        // Max-Heap для Heap Sort
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int zahl : zahlen) {
            maxHeap.add(zahl);
        }
        
        int[] sortiert = new int[zahlen.length];
        for (int i = 0; i < zahlen.length; i++) {
            sortiert[i] = maxHeap.remove();
        }
        
        System.out.println("Sortiert: " + Arrays.toString(sortiert));
    }
}

5. Бинарное дерево и BST

import java.util.*;

// Узел бинарного дерева
class TreeNode<T> {
    T wert;
    TreeNode<T> links;
    TreeNode<T> rechts;
    
    public TreeNode(T wert) {
        this.wert = wert;
        this.links = null;
        this.rechts = null;
    }
}

// Бинарное дерево поиска
class BinarySearchTree<T extends Comparable<T>> {
    private TreeNode<T> wurzel;
    
    public void insert(T wert) {
        wurzel = insertRecursive(wurzel, wert);
    }
    
    private TreeNode<T> insertRecursive(TreeNode<T> knoten, T wert) {
        if (knoten == null) {
            return new TreeNode<>(wert);
        }
        
        if (wert.compareTo(knoten.wert) < 0) {
            knoten.links = insertRecursive(knoten.links, wert);
        } else if (wert.compareTo(knoten.wert) > 0) {
            knoten.rechts = insertRecursive(knoten.rechts, wert);
        }
        
        return knoten;
    }
    
    public boolean search(T wert) {
        return searchRecursive(wurzel, wert);
    }
    
    private boolean searchRecursive(TreeNode<T> knoten, T wert) {
        if (knoten == null) {
            return false;
        }
        
        if (wert.equals(knoten.wert)) {
            return true;
        }
        
        return wert.compareTo(knoten.wert) < 0 
            ? searchRecursive(knoten.links, wert)
            : searchRecursive(knoten.rechts, wert);
    }
    
    public void inorder() {
        inorderRecursive(wurzel);
        System.out.println();
    }
    
    private void inorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            inorderRecursive(knoten.links);
            System.out.print(knoten.wert + " ");
            inorderRecursive(knoten.rechts);
        }
    }
    
    public void preorder() {
        preorderRecursive(wurzel);
        System.out.println();
    }
    
    private void preorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            System.out.print(knoten.wert + " ");
            preorderRecursive(knoten.links);
            preorderRecursive(knoten.rechts);
        }
    }
    
    public void postorder() {
        postorderRecursive(wurzel);
        System.out.println();
    }
    
    private void postorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            postorderRecursive(knoten.links);
            postorderRecursive(knoten.rechts);
            System.out.print(knoten.wert + " ");
        }
    }
}

// Применение BST
public class BaumDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Добавление элементов
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        System.out.println("In-Order Traversal (sortiert):");
        bst.inorder(); // 20 30 40 50 60 70 80
        
        System.out.println("Pre-Order Traversal:");
        bst.preorder(); // 50 30 20 40 70 60 80
        
        System.out.println("Post-Order Traversal:");
        bst.postorder(); // 20 40 30 60 80 70 50
        
        // Поиск
        System.out.println("Suche 40: " + bst.search(40)); // true
        System.out.println("Suche 25: " + bst.search(25)); // false
        
        // Сравнение производительности BST и массива
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 10000;
        Random random = new Random();
        
        // Создание BST
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Создание массива
        List<Integer> array = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            array.add(random.nextInt(GROESSE * 10));
        }
        
        int suchZahl = random.nextInt(GROESSE * 10);
        
        // Поиск в BST, O(log n) в среднем
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Поиск в массиве, O(n)
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("\nPerformance Vergleich:");
        System.out.println("BST Suche: " + bstZeit / 1000 + " μs, gefunden: " + bstGefunden);
        System.out.println("Array Suche: " + arrayZeit / 1000 + " μs, gefunden: " + arrayGefunden);
    }
}

Обзор Big-O нотации

Временная сложность

Операция	Array	Stack	Queue	Heap	BST	Graph
Доступ	O(1)	O(n)	O(n)	O(1)	O(log n)	O(V+E)
Поиск	O(n)	O(n)	O(n)	O(n)	O(log n)	O(V+E)
Вставка	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(1)
Удаление	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(V+E)

Пространственная сложность

Структура данных	Память
Array	O(n)
Stack	O(n)
Queue	O(n)
Heap	O(n)
BST	O(n)
Graph	O(V+E)

Алгоритмы работы с графами

Реализация графа

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjazenzliste;
    
    public Graph() {
        this.adjazenzliste = new HashMap<>();
    }
    
    public void kanteHinzufuegen(int u, int v) {
        adjazenzliste.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjazenzliste.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // Ungerichtet
    }
    
    // Breadth-First Search (BFS)
    public void bfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        besucht.add(start);
        
        while (!queue.isEmpty()) {
            int knoten = queue.remove();
            System.out.print(knoten + " ");
            
            for (int nachbar : adjazenzliste.getOrDefault(knoten, Collections.emptyList())) {
                if (!besucht.contains(nachbar)) {
                    besucht.add(nachbar);
                    queue.add(nachbar);
                }
            }
        }
        System.out.println();
    }
    
    // Depth-First Search (DFS)
    public void dfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        dfsRecursive(start, besucht);
        System.out.println();
    }
    
    private void dfsRecursive(int knoten, Set<Integer> besucht) {
        besucht.add(knoten);
        System.out.print(knoten + " ");
        
        for (int nachbar : adjazenzliste.getOrDefault(knoten, Collections.emptyList())) {
            if (!besucht.contains(nachbar)) {
                dfsRecursive(nachbar, besucht);
            }
        }
    }
}

// Graph Anwendung
public class GraphDemo {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // Kanten hinzufügen
        graph.kanteHinzufuegen(0, 1);
        graph.kanteHinzufuegen(0, 2);
        graph.kanteHinzufuegen(1, 3);
        graph.kanteHinzufuegen(2, 4);
        graph.kanteHinzufuegen(3, 4);
        graph.kanteHinzufuegen(4, 5);
        
        System.out.println("BFS ab Knoten 0:");
        graph.bfs(0); // 0 1 2 3 4 5
        
        System.out.println("DFS ab Knoten 0:");
        graph.dfs(0); // 0 1 3 4 2 5
    }
}

Преимущества и недостатки

Array

• Преимущества: прямой доступ за O(1), простая реализация
• Недостатки: фиксированный размер, вставка и удаление O(n)

Stack

• Преимущества: простая LIFO логика, push и pop за O(1)
• Недостатки: доступ только к верхнему элементу

Queue

• Преимущества: FIFO логика, справедливое распределение в очередях
• Недостатки: вставка в конец может быть дорогой операцией

Heap

• Преимущества: доступ к минимуму или максимуму за O(1)
• Недостатки: более сложная реализация

Дерево

• Преимущества: эффективный поиск O(log n), упорядоченные данные
• Недостатки: требуется балансировка

Graph

• Преимущества: гибкое представление связей, реалистичное моделирование
• Недостатки: сложные алгоритмы, высокие требования по памяти

Типичные вопросы на экзаменах

1. В чём разница между Stack и Queue? Stack использует принцип LIFO, Queue работает по принципу FIFO.

2. Объясните Big-O нотацию для поиска в массиве! Линейный поиск имеет сложность O(n) в худшем случае, прямой доступ требует O(1).

3. Когда использовать Heap вместо Array? Когда требуется частый доступ к минимальному или максимальному элементу (Priority Queue).

4. Чем отличаются BFS и DFS? BFS проходит граф уровень за уровнем с помощью Queue, DFS идёт в глубину, используя Stack или рекурсию.

Основные источники

1. https://de.wikipedia.org/wiki/Datenstruktur
2. https://www.geeksforgeeks.org/data-structures/
3. https://docs.oracle.com/javase/tutorial/collections/interfaces/index.html