Обзор структур данных: массив, стек, очередь, куча, дерево и граф

Этот материал дает краткий обзор основных структур данных с анализом производительности, областями применения и нотацией Big-O.

Суть в двух словах

Массив, стек, очередь, куча, дерево и граф составляют основу эффективных алгоритмов. Они отличаются временем доступа, требованиями к памяти и сферами применения.

Краткое описание

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

Сводка по производительности:

Массив

Доступ: O(1) - прямой доступ по индексу
Вставка/удаление: O(n) - требует сдвига элементов
Память: O(n) - смежные области памяти
Применение: фиксированный размер, частый случайный доступ

Стек (LIFO)

Push/Pop: O(1) - работа только с верхушкой
Память: O(n) - динамическое или фиксированное выделение
Применение: вызовы методов, backtracking, парсеры

Очередь (FIFO)

Enqueue/Dequeue: O(1) - операции в начале и конце
Память: O(n) - возможна циклическая реализация
Применение: буферы, BFS, очереди ожидания

Куча (приоритетная очередь)

Insert: O(log n) - сохранение свойства кучи
Extract Min/Max: O(log n) - удаление корня
Peek: O(1) - просмотр минимума/максимума
Применение: приоритеты, планирование задач, сортировка кучей

Дерево (бинарное дерево поиска)

Поиск: O(log n) - сбалансированное дерево
Вставка/удаление: O(log n) - сбалансированное дерево
Память: O(n) - на основе узлов
Применение: упорядоченные данные, базы данных

Граф

Обход: O(V+E) - V узлы, E рёбра
Память: O(V+E) - список смежности
Применение: сети, планирование маршрутов

Ключевые моменты для запоминания

Массив: O(1) доступ, фиксированный размер, смежная память
Стек: принцип LIFO, push/pop за O(1), call stack
Очередь: принцип FIFO, enqueue/dequeue за O(1), буферы
Куча: приоритетная очередь, insert/extract за O(log n), peek за O(1)
Дерево: иерархическая структура, O(log n) при сбалансировке, BST
Граф: структура узел-ребро, BFS/DFS за O(V+E)
Нотация Big-O: анализ временной и пространственной сложности
Практическое применение: выбор оптимальной структуры для задачи

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

Массив: индексированная коллекция с прямым доступом
Стек: структура LIFO для отслеживания истории
Очередь: структура FIFO для обработки задач в порядке поступления
Куча: приоритетная древовидная структура
Дерево: иерархия узлов с отношениями родитель-потомок
Граф: сеть узлов и рёбер
Производительность: анализ операций с помощью Big-O
Применение: выбор правильной структуры для решения

Примеры из практики

1. Производительность массива и ArrayList

import java.util.*;

public class ArrayPerformance {
    public static void main(String[] args) {
        final int GROESSE = 100_000;
        
        // Array (feste Größe)
        long start = System.nanoTime();
        int[] array = new int[GROESSE];
        for (int i = 0; i < GROESSE; i++) {
            array[i] = i; // O(1) Schreiben
        }
        long arrayZeit = System.nanoTime() - start;
        
        // ArrayList (dynamisch)
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            arrayList.add(i); // O(1) amortisiert
        }
        long arrayListZeit = System.nanoTime() - start;
        
        // Random Access Test
        Random random = new Random();
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int index = random.nextInt(GROESSE);
            int wert = array[index]; // O(1)
        }
        long arrayAccess = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int index = random.nextInt(GROESSE);
            int wert = arrayList.get(index); // O(1)
        }
        long arrayListAccess = System.nanoTime() - start;
        
        System.out.println("Array Füllzeit: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList Füllzeit: " + arrayListZeit / 1_000_000 + " ms");
        System.out.println("Array Access: " + arrayAccess / 1000 + " μs");
        System.out.println("ArrayList Access: " + arrayListAccess / 1000 + " μs");
    }
}

2. Применение стека и очереди

import java.util.*;

public class StackQueueDemo {
    public static void main(String[] args) {
        // Stack для Klammerprüfung (LIFO)
        String ausdruck = "{[()()]}";
        if (pruefeKlammer(ausdruck)) {
            System.out.println("Ausdruck '" + ausdruck + "' ist gültig");
        }
        
        // Queue für Druckerwarteschlange (FIFO)
        Queue<String> druckerQueue = new LinkedList<>();
        druckerQueue.add("Dokument1.pdf");
        druckerQueue.add("Dokument2.pdf");
        druckerQueue.add("Dokument3.pdf");
        
        System.out.println("Druckerwarteschlange:");
        while (!druckerQueue.isEmpty()) {
            String dokument = druckerQueue.remove();
            System.out.println("Drucke: " + dokument);
        }
        
        // Performance Vergleich
        performanceVergleich();
    }
    
    // Klammerprüfung mit Stack
    private 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();
    }
    
    private static void performanceVergleich() {
        final int OPERATIONEN = 1_000_000;
        
        // Stack Performance
        long start = System.nanoTime();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < OPERATIONEN; i++) {
            stack.push(i);
        }
        for (int i = 0; i < OPERATIONEN; i++) {
            stack.pop();
        }
        long stackZeit = System.nanoTime() - start;
        
        // Queue Performance
        start = System.nanoTime();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < OPERATIONEN; i++) {
            queue.add(i);
        }
        for (int i = 0; i < OPERATIONEN; i++) {
            queue.remove();
        }
        long queueZeit = System.nanoTime() - start;
        
        System.out.println("\nPerformance Vergleich (" + OPERATIONEN + " Operationen):");
        System.out.println("Stack Zeit: " + stackZeit / 1_000_000 + " ms");
        System.out.println("Queue Zeit: " + queueZeit / 1_000_000 + " ms");
    }
}

3. Применение приоритетной очереди (куча)

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Min-Heap для aufsteigende Sortierung
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(40);
        minHeap.add(5);
        
        System.out.println("Min-Heap (Priority Queue):");
        while (!minHeap.isEmpty()) {
            System.out.println("Extract Min: " + minHeap.remove());
        }
        
        // Max-Heap mit Comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(40);
        maxHeap.add(5);
        
        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println("Extract Max: " + maxHeap.remove());
        }
        
        // Task-Scheduling mit Prioritäten
        taskSchedulingDemo();
    }
    
    private static void taskSchedulingDemo() {
        // Task mit Priorität
        class Task {
            String name;
            int priority;
            
            Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
            
            @Override
            public String toString() {
                return name + " (Prio: " + priority + ")";
            }
        }
        
        // Priority Queue für Tasks
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            (t1, t2) -> Integer.compare(t2.priority, t1.priority) // Max-Heap
        );
        
        taskQueue.add(new Task("Email senden", 2));
        taskQueue.add(new Task("Datenbank backup", 5));
        taskQueue.add(new Task("Log analysieren", 1));
        taskQueue.add(new Task("Security update", 10));
        
        System.out.println("\nTask-Scheduling (hohe Priorität zuerst):");
        while (!taskQueue.isEmpty()) {
            System.out.println("Ausführen: " + taskQueue.remove());
        }
    }
}

4. Поиск в бинарном дереве против поиска в массиве

import java.util.*;

class TreeNode {
    int wert;
    TreeNode links, rechts;
    
    TreeNode(int wert) {
        this.wert = wert;
        this.links = this.rechts = null;
    }
}

class BinarySearchTree {
    TreeNode wurzel;
    
    void insert(int wert) {
        wurzel = insertRecursive(wurzel, wert);
    }
    
    private TreeNode insertRecursive(TreeNode knoten, int wert) {
        if (knoten == null) {
            return new TreeNode(wert);
        }
        
        if (wert < knoten.wert) {
            knoten.links = insertRecursive(knoten.links, wert);
        } else if (wert > knoten.wert) {
            knoten.rechts = insertRecursive(knoten.rechts, wert);
        }
        
        return knoten;
    }
    
    boolean search(int wert) {
        return searchRecursive(wurzel, wert);
    }
    
    private boolean searchRecursive(TreeNode knoten, int wert) {
        if (knoten == null) return false;
        if (knoten.wert == wert) return true;
        
        return wert < knoten.wert 
            ? searchRecursive(knoten.links, wert)
            : searchRecursive(knoten.rechts, wert);
    }
}

public class SuchbaumVsArray {
    public static void main(String[] args) {
        final int GROESSE = 100_000;
        Random random = new Random();
        
        // BST aufbauen
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Array erstellen
        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 Suche O(log n) im Durchschnitt
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Array Suche O(n) im Worst-Case
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("Suche nach " + suchZahl + ":");
        System.out.println("BST Zeit: " + bstZeit / 1000 + " μs, gefunden: " + bstGefunden);
        System.out.println("Array Zeit: " + arrayZeit / 1000 + " μs, gefunden: " + arrayGefunden);
        
        // Sortierter Array (Binary Search)
        Collections.sort(array);
        start = System.nanoTime();
        int index = Collections.binarySearch(array, suchZahl);
        long binaryZeit = System.nanoTime() - start;
        
        System.out.println("Binary Search Zeit: " + binaryZeit / 1000 + " μs, Index: " + index);
    }
}

5. Сравнение методов обхода графа

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjazenzliste = new HashMap<>();
    
    void kanteHinzufuegen(int u, int v) {
        adjazenzliste.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjazenzliste.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }
    
    // Breadth-First Search (Queue)
    void bfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        besucht.add(start);
        
        System.out.print("BFS: ");
        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 (Stack/Rekursion)
    void dfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        dfsRecursive(start, besucht);
    }
    
    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);
            }
        }
    }
}

public class GraphTraversal {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // Graph aufbauen
        graph.kanteHinzufuegen(0, 1);
        graph.kanteHinzufuegen(0, 2);
        graph.kanteHinzufuegen(1, 3);
        graph.kanteHinzufuegen(2, 4);
        graph.kanteHinzufuegen(3, 4);
        graph.ketteHinzufuegen(4, 5);
        
        System.out.println("Graph Traversierung:");
        graph.bfs(0); // Level-order: 0 1 2 3 4 5
        graph.dfs(0); // Depth-first: 0 1 3 4 2 5
    }
}

Таблица сравнения нотации 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)	V = вершины, E = рёбра

Сценарии применения

Выбор структуры данных

Используйте массив, когда:

Размер известен и постоянен
Требуется частый случайный доступ
Критична экономия памяти (непрерывное расположение)

Используйте стек, когда:

Нужно поведение LIFO
Требуется отслеживание состояний
Нужно управлять вызовами рекурсивных функций

Используйте очередь, когда:

Нужно поведение FIFO
Нужно реализовать очереди ожидания
Используется поиск в ширину

Используйте кучу, когда:

Важны приоритеты
Часто обращаются к минимуму или максимуму
Работают с алгоритмами планирования

Используйте дерево, когда:

Хранят упорядоченные данные
Требуется эффективный поиск
Нужно представить иерархические отношения

Используйте граф, когда:

Моделируют сетевые отношения
Требуется планирование маршрутов
Есть отношения “многие ко многим”

Советы по оптимизации производительности

Оптимизация массива

// Подготовка цикла
int[] array = new int[1000];
int laenge = array.length; // Не в каждой итерации

for (int i = 0; i < laenge; i++) {
    array[i] = i;
}

Оптимизация стека

// Массив вместо стека для фиксированного размера
int[] stack = new int[1000];
int top = -1;

void push(int wert) {
    stack[++top] = wert;
}

int pop() {
    return stack[top--];
}

Оптимизация очереди

// Циклическая очередь для фиксированного размера
int[] queue = new int[1000];
int front = 0, rear = 0;

void enqueue(int wert) {
    queue[rear = (rear + 1) % queue.length] = wert;
}

int dequeue() {
    return queue[front = (front + 1) % queue.length];
}

Частые вопросы на экзаменах

Какую структуру данных использовать для очереди принтера? Очередь (FIFO), так как первый запрос обрабатывается первым.
Почему поиск в BST быстрее, чем поиск в массиве? BST: O(log n) благодаря дихотомии, массив: O(n) из-за линейного поиска.
В чём разница между стеком и очередью? Стек: LIFO (последний пришёл, первый ушёл), очередь: FIFO (первый пришёл, первый ушёл).
Когда использовать кучу вместо массива? Когда часто обращаются к минимуму или максимуму (приоритетная очередь).

Täglicher Artikel

Структуры данных: Array, Stack, Queue, Heap, Tree, Graph

Обзор структур данных: массив, стек, очередь, куча, дерево и граф

Суть в двух словах

Краткое описание

Массив

Стек (LIFO)

Очередь (FIFO)

Куча (приоритетная очередь)

Дерево (бинарное дерево поиска)

Граф

Ключевые моменты для запоминания

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

Примеры из практики

1. Производительность массива и ArrayList

2. Применение стека и очереди

3. Применение приоритетной очереди (куча)

4. Поиск в бинарном дереве против поиска в массиве

5. Сравнение методов обхода графа

Таблица сравнения нотации Big-O

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

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

Сценарии применения

Выбор структуры данных

Советы по оптимизации производительности

Оптимизация массива

Оптимизация стека

Оптимизация очереди

Частые вопросы на экзаменах

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

Nächster Artikel in Алгоритмы

Похожие статьи

Структуры данных: Stack, Queue, Heap, Array, Tree, Graph

Стандартные алгоритмы: поиск и сортировка

Адаптивный код Хаффмана: динамическое сжатие данных для учащихся

Täglicher Artikel

Обзор структур данных: массив, стек, очередь, куча, дерево и граф

IRC-Mania Die Seite rund um Sicherheit und Programmierung

Суть в двух словах

Краткое описание

Массив

Стек (LIFO)

Очередь (FIFO)

Куча (приоритетная очередь)

Дерево (бинарное дерево поиска)

Граф

Ключевые моменты для запоминания

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

Примеры из практики

1. Производительность массива и ArrayList

2. Применение стека и очереди

3. Применение приоритетной очереди (куча)

4. Поиск в бинарном дереве против поиска в массиве

5. Сравнение методов обхода графа

IRC-Security.de

Таблица сравнения нотации Big-O

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

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

Сценарии применения

Выбор структуры данных

Советы по оптимизации производительности

Оптимизация массива

Оптимизация стека

Оптимизация очереди

Частые вопросы на экзаменах

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

Premium VPS Hosting

Nächster Artikel in Алгоритмы

Похожие статьи

Структуры данных: Stack, Queue, Heap, Array, Tree, Graph

Стандартные алгоритмы: поиск и сортировка

Адаптивный код Хаффмана: динамическое сжатие данных для учащихся