Что такое Stack?

📚 Что такое Stack (Стек)

Stack (Стек) — это абстрактный тип данных, представляющий собой коллекцию элементов, работающую по принципу LIFO (Last In, First Out — «последним пришёл, первым ушёл»). Это означает, что элемент, добавленный последним, будет извлечён первым. Стек можно сравнить со стопкой тарелок: новую тарелку кладут сверху, и снимают также сверху.

---

🎯 Основные операции стека

У стека есть две ключевые операции:

1. Push — добавление элемента на вершину стека.
2. Pop — удаление и возврат элемента с вершины стека.

Дополнительные часто используемые операции:

• Peek (или Top) — просмотр элемента на вершине без удаления.
• IsEmpty — проверка, пуст ли стек.
• Count — получение количества элементов.

---

💻 Реализация стека в C#

В C# стек можно реализовать несколькими способами:

1. Использование встроенного класса Stack<T> (из пространства имён System.Collections.Generic)

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Создание стека целых чисел
        Stack<int> stack = new Stack<int>();
        
        // Push — добавление элементов
        stack.Push(10);
        stack.Push(20);
        stack.Push(30);
        
        // Peek — просмотр верхнего элемента (без удаления)
        Console.WriteLine($"Верхний элемент: {stack.Peek()}"); // 30
        
        // Pop — извлечение элементов (в порядке LIFO)
        Console.WriteLine($"Извлечено: {stack.Pop()}"); // 30
        Console.WriteLine($"Извлечено: {stack.Pop()}"); // 20
        
        // Проверка количества элементов
        Console.WriteLine($"Количество элементов: {stack.Count}"); // 1
        
        // Проверка на пустоту
        Console.WriteLine($"Стек пуст? {stack.Count == 0}"); // False
    }
}

2. Реализация стека с помощью массива (упрощённая версия)

public class ArrayStack<T>
{
    private T[] _items;
    private int _top;
    
    public ArrayStack(int capacity = 10)
    {
        _items = new T[capacity];
        _top = -1;
    }
    
    public void Push(T item)
    {
        if (_top == _items.Length - 1)
        {
            Array.Resize(ref _items, _items.Length * 2);
        }
        
        _items[++_top] = item;
    }
    
    public T Pop()
    {
        if (_top == -1)
            throw new InvalidOperationException("Стек пуст");
        
        return _items[_top--];
    }
    
    public T Peek()
    {
        if (_top == -1)
            throw new InvalidOperationException("Стек пуст");
        
        return _items[_top];
    }
    
    public bool IsEmpty => _top == -1;
    public int Count => _top + 1;
}

---

🔄 Стек вызовов (Call Stack) — самый важный пример

В контексте C# и .NET стек вызовов (call stack) — это критически важная структура данных, которую использует среда выполнения для управления выполнением программы:

• Каждый вызов метода помещает новый фрейм стека (stack frame) в стек вызовов
• Фрейм стека содержит локальные переменные, параметры метода и адрес возврата
• При завершении метода его фрейм извлекается из стека
• Рекурсивные вызовы создают множественные фреймы в стеке

class CallStackDemo
{
    static void Main()
    {
        MethodA();
    }
    
    static void MethodA()
    {
        MethodB();  // Добавляется фрейм MethodB поверх MethodA
    }
    
    static void MethodB()
    {
        // В этот момент стек вызовов содержит (снизу вверх):
        // 1. Main()
        // 2. MethodA()
        // 3. MethodB() ← вершина стека
        Console.WriteLine("Выполняется MethodB");
    }
}

---

🚀 Практическое применение стека

1. Отмена операций (Undo/Redo)

public class TextEditor
{
    private Stack<string> _undoStack = new Stack<string>();
    private Stack<string> _redoStack = new Stack<string>();
    private string _currentText = "";
    
    public void Type(string text)
    {
        _undoStack.Push(_currentText);
        _currentText += text;
        _redoStack.Clear();
    }
    
    public void Undo()
    {
        if (_undoStack.Count > 0)
        {
            _redoStack.Push(_currentText);
            _currentText = _undoStack.Pop();
        }
    }
}

2. Проверка сбалансированности скобок

public bool AreBracketsBalanced(string expression)
{
    Stack<char> stack = new Stack<char>();
    
    foreach (char ch in expression)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.Push(ch);
        }
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (stack.Count == 0) return false;
            
            char top = stack.Pop();
            if (!IsMatchingPair(top, ch)) return false;
        }
    }
    
    return stack.Count == 0;
}

3. Обход графов (Depth-First Search)

public void DFS(Node start)
{
    Stack<Node> stack = new Stack<Node>();
    HashSet<Node> visited = new HashSet<Node>();
    
    stack.Push(start);
    
    while (stack.Count > 0)
    {
        Node current = stack.Pop();
        
        if (!visited.Contains(current))
        {
            visited.Add(current);
            Process(current);
            
            foreach (Node neighbor in current.Neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    stack.Push(neighbor);
                }
            }
        }
    }
}

---

⚡ Производительность и особенности реализации

Встроенный Stack<T> в .NET:

• Внутренняя реализация: использует массив
• Сложность операций:
  • Push(): O(1) (амортизированная)
  • Pop(): O(1)
  • Peek(): O(1)
• Потокобезопасность: Нет (для многопоточности используйте ConcurrentStack<T>)

Когда использовать стек:

• Обработка рекурсивных алгоритмов
• Синтаксический анализ и преобразование выражений
• Навигация по истории (браузер, приложения)
• Алгоритмы обхода графов и деревьев
• Управление состоянием в конечных автоматах

---

🎓 Заключение

Стек — фундаментальная структура данных, которая играет ключевую роль не только в разработке алгоритмов, но и в самой работе среды выполнения .NET. Понимание стека критически важно для:

• Отладки сложных вызовов методов
• Оптимизации использования памяти
• Реализации алгоритмов обхода
• Понимания механизма работы исключений (исключения также используют стек вызовов для формирования трассировки)

В C# разработке знание стека помогает писать более эффективный код, правильно работать с рекурсией и понимать внутренние механизмы платформы .NET.