Какая коллекция стек?

Что такое стек (Stack) в программировании?

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

Ключевые операции со стеком

Основные операции, которые определяют поведение стека:

• Push — добавление элемента на вершину стека.
• Pop — удаление и возврат элемента с вершины стека. Если стек пуст, эта операция обычно вызывает ошибку или исключение.
• Peek (или Top) — возврат элемента с вершины стека без его удаления. Позволяет "заглянуть" в вершину.
• IsEmpty — проверка, пуст ли стек.
• Count (или Size) — получение количества элементов в стеке.

Реализация и использование стека в C# (Unity)

В C#, который является основным языком разработки в Unity, стек представлен универсальным классом System.Collections.Generic.Stack<T>.

Базовый пример использования

using System.Collections.Generic;
using UnityEngine;

public class StackExample : MonoBehaviour
{
    void Start()
    {
        // Создание нового стека для хранения целых чисел
        Stack<int> numberStack = new Stack<int>();

        // Push: Добавление элементов в стек
        numberStack.Push(10); // Стек: [10] (вершина)
        numberStack.Push(20); // Стек: [20, 10]
        numberStack.Push(30); // Стек: [30, 20, 10]

        // Peek: Посмотреть на вершину без удаления
        Debug.Log("Вершина стека (Peek): " + numberStack.Peek()); // Выведет: 30
        // Стек остался: [30, 20, 10]

        // Pop: Извлечение элементов из стека
        int poppedItem = numberStack.Pop(); // Извлекает 30
        Debug.Log("Извлечённый элемент (Pop): " + poppedItem); // Выведет: 30
        // Теперь стек: [20, 10]

        Debug.Log("Следующая вершина: " + numberStack.Peek()); // Выведет: 20

        // Проверка на пустоту и обход
        while (numberStack.Count > 0)
        {
            int item = numberStack.Pop();
            Debug.Log("Извлечено в цикле: " + item);
        }
        // Последовательность вывода: 20, 10

        Debug.Log("Стек пуст? " + (numberStack.Count == 0)); // Выведет: True
    }
}

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

Стек — незаменимая структура данных во многих алгоритмах и игровых механиках:

1. Система отмены действий (Undo/Redo)

Каждое действие игрока (перемещение объекта, изменение цвета) можно сохранять как объект команды и помещать в стек undoStack. При отмене из этого стека извлекается последняя команда и выполняется обратное действие. Отменённые команды часто помещаются в отдельный стек redoStack.

Stack<ICommand> undoStack = new Stack<ICommand>();
Stack<ICommand> redoStack = new Stack<ICommand>();

public void ExecuteCommand(ICommand command)
{
    command.Execute();
    undoStack.Push(command);
    redoStack.Clear(); // Новая команда очищает историю повторов
}

public void Undo()
{
    if (undoStack.Count > 0)
    {
        ICommand command = undoStack.Pop();
        command.Undo();
        redoStack.Push(command);
    }
}

2. Управление состояниями игры или UI

Стек идеально подходит для управления экранами интерфейса (меню, инвентарь, окна настроек). При открытии нового окна текущее состояние помещается в стек, а при закрытии — восстанавливается предыдущее.

Stack<UIScreen> screenStack = new Stack<UIScreen>();

public void OpenScreen(UIScreen newScreen)
{
    if (screenStack.Count > 0)
        screenStack.Peek().Hide();

    newScreen.Show();
    screenStack.Push(newScreen);
}

public void CloseCurrentScreen()
{
    if (screenStack.Count > 0)
    {
        screenStack.Pop().Hide();
        
        if (screenStack.Count > 0)
            screenStack.Peek().Show();
    }
}

3. Обход графов и алгоритмы поиска

Стек является основой для нерекурсивного обхода дерева или графа в глубину (Depth-First Search, DFS). Также стек используется для проверки корректности расстановки скобок в выражениях.

4. Система истории навигации

В мобильных играх или приложениях можно хранить историю посещений различных разделов в стеке, чтобы обеспечить корректную работу кнопки "Назад".

Важные замечания

• Неиндексируемый доступ: В отличие от списка (List<T>), вы не можете получить произвольный элемент стека по индексу. Доступ возможен только к элементу на вершине.
• Порядок итерации: При простом переборе стека через foreach элементы возвращаются в порядке от вершины к основанию (то есть в порядке, обратном добавлению).
• Производительность: Все основные операции (Push, Pop, Peek) выполняются за константное время O(1), что делает стек высокопроизводительной структурой данных.
• Стек вызовов (Call Stack): Важно не путать структуру данных "стек" с стеком вызовов в исполняемой среде, который отслеживает вызовы методов, хотя принцип работы у них одинаковый (LIFO).

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