Стек

Стек(stack) - это абстрактная структура данных, в которой элементы организованы по принципу LIFO(Last In First Out - “пришел последним, вышел первым”).

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

Алгоритм работы стека, в самой простой реализации, следующий:

  • каждый новый элемент добавляется в вершину стека при этом все последующие элементы смещаются на одну позицию вниз;
  • мы можем получить из стека только элемент расположенный в вершине(его также называют головным элементом), при этом он удаляется из стека, а последующие - смещаются на позицию вверх;

Таким образом, если стек не пустой, в его вершине всегда располагается последний добавленный элемент, с которым мы и можем взаимодействовать.

В библиотеке System.Collections.Generic языка C#, уже есть реализация .Net класса Stack, однако для понимания устройства этой структуры данных, напишем свою реализацию стека.

Стандартно для стека реализуют три операции:

  • Push - метод добавления нового элемента в вершину;
  • Pop - чтение элемента с его удалением;
  • Peek - чтение головного элемента без удаления из стека.

Мы добавим к этим операциям следующие:

  • Size - получение размера структуры stack;
  • Clear - метод для очистки стека.

Стек на основе массива

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

using System;

public class StackFixed<T>
{
    private int _currentSize; // текущий размер стека
    private T[] _dataArray; // данные стека
    private int _stackMaxSize; //максимальное количество элементов в стеке
    // конструктор
    public StackFixed(int stackMaxSize)
    {
        _dataArray = new T[stackMaxSize];
        _currentSize = 0;
        _stackMaxSize = stackMaxSize;
    }

    // метод для получения размера стека
    public int Size()
    {
        return _currentSize;
    }

    // добавление нового элемента
    public void Push(T item)
    {
        // если текущий размер равен максимальному, то смещаем стек на одну позицию
        // при этом первый элемент удаляется
        if (_currentSize == _stackMaxSize)
        {
            RebuildData();
        }

        _dataArray[_currentSize] = item;
        _currentSize++;
    }

    // чтение главного элемента стека без удаления
    public T Peek()
    {
        // если данных нет, выбрасываем исключение
        if (Size() == 0)
        {
            throw new Exception("Stack is empty");
        }

        return _dataArray[_currentSize - 1];
    }

    // извлечение элемента
    public T Pop()
    {
        var item = Peek();
        _currentSize--;
        return item;
    }

    // очистка стека
    public void Clear()
    {
        _dataArray = new T[_stackMaxSize];
        _currentSize = 0;
    }

    private void RebuildData()
    {
        var newData = new T[_stackMaxSize];
        for (var i = 1; i < _dataArray.Length; i++)
        {
            newData[i - 1] = _dataArray[i];
        }

        _dataArray = newData;
        _currentSize = _stackMaxSize - 1;
    }
}

Такой же алгоритм выполнен в буфере клавиатуры. Он может содержать фиксированное количество информации о нажатии клавиш, при переполнении буфера, старые данные затираются новыми.

При необходимости можно переписать метод RebuildData таким образом, чтобы он изменял размер массива если значения не помещаются:

private void RebuildData()
{
    _stackMaxSize += 10;
    var d = new T[_stackMaxSize];
    Array.Copy(_dataArray, d, _dataArray.Length);
    _dataArray = d;
}

Пример использования фиксированного стека

private static void Main(string[] args)
{
    var stackFixed = new StackFixed<string>(5);

    stackFixed.Push("Lora");
    stackFixed.Push("Dale");
    stackFixed.Push("Jack");
    stackFixed.Push("Andrew");
    stackFixed.Push("Linda");
    stackFixed.Push("Lisa");

    while (stackFixed.Size() > 0)
    {
        Console.WriteLine(stackFixed.Pop());
    }

    Console.ReadLine();
}

В результате выполнения программа выведет на экран 5 последних добавленных имен:

Стек на основе списка(List)

Для хранения данных стека, будем использовать коллекцию List из стандартной библиотеки платформы .Net System.Collections.Generic.

using System;
using System.Collections.Generic;

public class Stack<T>
{
    private int _size; // текущий размер стека
    private readonly List<T> _data; // данные стека
    // конструктор
    public Stack()
    {
        _data = new List<T>();
        _size = 0;
    }

    // метод для получения размера стека
    public int Size()
    {
        return _size;
    }

    // добавление нового элемента
    public void Push(T item)
    {
        _data.Add(item);
        _size++;
    }

    // чтение главного элемента стека без удаления
    public T Peek()
    {
        // если данных нет, выбрасываем исключение
        if (Size() == 0)
        {
            throw new Exception("Stack is empty");
        }

        return _data[_size - 1];
    }

    // извлечение элемента
    public T Pop()
    {
        var item = Peek();
        _data.Remove(item);
        _size--;
        return item;
    }

    // очистка стека
    public void Clear()
    {
        _data.Clear();
        _size = 0;
    }
}

Используя List для хранения данных, у нас нет необходимости следить за количеством объектов помещенных в стек, как это было в классе с массивом. Список автоматически расширяется при добавлении новых значений.

Смотрите также: