Алгоритмы и структуры данных на C#: практическое руководство

Алгоритмы и структуры данных на C#: от теории к практике

Понимание алгоритмов и структур данных — фундамент профессиональной разработки на C#. Независимо от того, пишете ли вы высоконагруженное веб-приложение на ASP.NET Core или десктопное приложение на WPF, выбор правильной структуры данных и эффективного алгоритма напрямую влияет на производительность, читаемость и масштабируемость кода. В этой статье мы разберем ключевые структуры данных и алгоритмы на конкретных примерах кода C#, которые вы сможете сразу применить в своих проектах.

1. Стек (Stack) и очередь (Queue) в C#

Стек (LIFO — Last In, First Out) и очередь (FIFO — First In, First Out) — базовые структуры данных, которые встроены в .NET и широко используются в реальных задачах: от обработки вызовов методов до управления задачами.

Стек на C#

Стек часто применяется для реализации "отката" действий (undo) или синтаксического анализа. В C# стек представлен классом Stack<T>.

using System;
using System.Collections.Generic;

public class StackExample
{
    public static void Main()
    {
        Stack<string> browserHistory = new Stack<string>();
        
        // Добавление элементов (Push)
        browserHistory.Push("Главная страница");
        browserHistory.Push("Новости");
        browserHistory.Push("Статья про C#");
        
        Console.WriteLine($"Последняя страница: {browserHistory.Peek()}"); // Статья про C#
        
        // Удаление и возврат верхнего элемента (Pop)
        string lastPage = browserHistory.Pop();
        Console.WriteLine($"Возвращаемся с: {lastPage}"); // Статья про C#
        Console.WriteLine($"Текущая страница: {browserHistory.Peek()}"); // Новости
    }
}

Очередь на C#

Очередь идеальна для обработки задач в порядке их поступления (например, очередь печати или обработка сообщений). Используйте класс Queue<T>.

using System;
using System.Collections.Generic;

public class QueueExample
{
    public static void Main()
    {
        Queue<string> printQueue = new Queue<string>();
        
        // Добавление в конец очереди (Enqueue)
        printQueue.Enqueue("Документ1.pdf");
        printQueue.Enqueue("Фото.png");
        printQueue.Enqueue("Отчет.docx");
        
        Console.WriteLine($"Первый на печать: {printQueue.Peek()}"); // Документ1.pdf
        
        // Удаление из начала очереди (Dequeue)
        string firstJob = printQueue.Dequeue();
        Console.WriteLine($"Печатается: {firstJob}"); // Документ1.pdf
        Console.WriteLine($"Следующий: {printQueue.Peek()}"); // Фото.png
    }
}

Важно: В .NET также есть ConcurrentQueue<T> для многопоточных сценариев и Stack<T> не поддерживает индексный доступ — только вершину.

2. Сортировка массива: быстрая сортировка (QuickSort)

Хотя в C# есть встроенный метод Array.Sort(), понимание алгоритмов сортировки необходимо для собеседований и оптимизации. Быстрая сортировка — один из самых эффективных алгоритмов со сложностью O(n log n) в среднем случае.

using System;

public class QuickSortExample
{
    public static void QuickSort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = Partition(arr, left, right);
            QuickSort(arr, left, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, right);
        }
    }

    private static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right]; // опорный элемент — последний
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                (arr[i], arr[j]) = (arr[j], arr[i]); // swap
            }
        }
        (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
        return i + 1;
    }

    public static void Main()
    {
        int[] numbers = { 34, 7, 23, 32, 5, 62 };
        Console.WriteLine("До сортировки: " + string.Join(", ", numbers));
        
        QuickSort(numbers, 0, numbers.Length - 1);
        
        Console.WriteLine("После сортировки: " + string.Join(", ", numbers));
        // Вывод: 5, 7, 23, 32, 34, 62
    }
}

Совет: Для больших массивов используйте Array.Sort() — он реализован с использованием интроспективной сортировки (гибрид QuickSort, HeapSort и InsertionSort).

3. Бинарный поиск (Binary Search) в отсортированном массиве

Бинарный поиск — классический алгоритм для поиска элемента в отсортированном массиве за O(log n). В C# есть встроенная реализация Array.BinarySearch(), но для понимания логики реализуем его вручную.

using System;

public class BinarySearchExample
{
    public static int BinarySearch(int[] sortedArr, int target)
    {
        int left = 0;
        int right = sortedArr.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2; // защита от переполнения

            if (sortedArr[mid] == target)
                return mid;
            else if (sortedArr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1; // элемент не найден
    }

    public static void Main()
    {
        int[] data = { 2, 5, 8, 12, 16, 23, 38, 45, 56, 72 };
        int target = 23;

        int index = BinarySearch(data, target);
        Console.WriteLine(index != -1 
            ? $"Элемент {target} найден на индексе {index}" 
            : $"Элемент {target} не найден");
        // Вывод: Элемент 23 найден на индексе 5
    }
}

Примечание: Всегда проверяйте, что массив отсортирован, иначе бинарный поиск выдаст некорректный результат.

4. Связный список (LinkedList) и его применение

В отличие от массива, связный список не требует непрерывного блока памяти и позволяет быстро вставлять/удалять элементы в середине. В .NET есть двусвязный список LinkedList<T>.

using System;
using System.Collections.Generic;

public class LinkedListExample
{
    public static void Main()
    {
        LinkedList<string> tasks = new LinkedList<string>();