Реализация стека при помощи массива на языке C#

18.05.2018admin

Как я и обещал, практически сразу после написания статьи про структуру данных стек — выйдет примерная очень simple реализация стека нативными средствами языка C#. Это простой и лёгкий в освоении алгоритм, понятный любому человеку, который хоть раз в жизни мыл тарелки 🙂

Несколько недель назад я писал свою собственную реализацию очереди и там же указывал, что писать подобный код необходимо только лишь для понимания алгоритма. В прод тянуть это, конечно, не рекомендуется. Тем более в составе стандартных коллекций .NET Framework существует уже готовый вариант — класс под названием Stack<T> (пространство имён System.Collections.Generic).

Давайте начнём. Первым делом создадим новый файл, в котором определим новый класс и назовём его Stack (встроенный стек фреймворка будет лежать в другом namespace, поэтому никаких конфликтов быть не должно). Обернём наш класс в Generic для большей гибкости и динамичности использования. Внутри объявим следующие локальные поля: целочисленные _Size (для хранения размера стека) и _Top. Последняя переменная служит маркером «верхушки» (головы) стека, чтобы мы всегда знали какой именно элемент нам доступен для считывания. Также, конечно, необходимо добавить массив типа T, назовём его простым и понятным _Array. _Size и _Array это readonly поля, т.е. присвоить им должное значение можно будет только в конструкторе в момент создания экземпляра класса.

Раз есть readonly поля, значит должен быть и конструктор, в котором мы должны задать размерность нашему основному массиву и присвоить этот размер в переменную _Size:

Сразу же, не отходя от кассы — инкапсулируем свойства Top и Size. Это важные и интересные данные, которые вполне возможно выносить наружу при помощи стандартного getter:

Также, желательно добавить свойство Count, возвращающее количество элементов в стеке:

Подготовительную часть можно считать завершённой. Теперь переходим к самому интересному — методы. Первыми на очереди будут IsFull и IsEmpty, служащие для понимания степени заполненности массива стека:

Следующими будут идти операционные функции Push, Peek и Pop. Как видно из названия, Push служит для добавления объекта в стек, Peek — для получение объекта самого верхнего уровня и Pop — для считывания этого самого объекта и удаления его из стека:

Здесь всё просто — _Top служит ориентиром, переменная хранящая верхний элемент стека. Верхняя тарелочка. При добавлении в методе Push мы вставляем в массив по индексу _Top элемент и после делаем инкремент этой переменной. Pop — возвращает «вычитывает» верхушку и декрементирует _Top (тем самым можно понять, что в нашей реализации удаления, зачистка элемента не происходит; мы просто «забываем» об элементе — он продолжает находится в памяти!). Peek — просто возвращает верхний элемент (маркер не изменяется).

При желании можно добавить свой личный GetEnumerator, чтобы при необходимости можно было перебрать все элементы стека сверху-вниз при помощи конструкции foreach. Для этого наш класс должен реализовывать интерфейс IEnumerable. У нас появится два новых метода:

Наш кастомный стек готов. Теперь необходимо его проверить в деле — напишем простой код, который будет работать с нашим классом. Допустим мы открыли склад — очень узкий и длинный; только с одним входом. По ширине и высоте этого абстрактного коридора можно поместить только одну коробку. Таким образом если мы ставим (пушим!) коробку на склад — она идеально входит и занимает своё место, если же мы ставим вторую коробку, то строго перед первой (задвигая первую коробку вглубь склада). Открывая двери склада мы всегда будем видеть последнюю коробку, которую туда поставили (наш с вами _Top). Принцип передвижения коробок похож на старую игру Sokoban и, да, это стек LIFO:

Результат выполнения данной программы будет следующий:

Custom simple Stack native C# .NET

Вот вроде и всё. Если же вам интересна «дотнетовская» реализация стека на C# — можно заглянуть в официальный репозиторий dotnet/corefx, в котором также есть файл Stack.cs. К слову, сам алгоритм стека не намного отличается от идей описанных в данной статье. Да, он более продуманный, конечно. И с возможностью динамического изменения размерности, и другими полезными функциями. Но статья была не сделать копию того, а написать простое и своё. С этим, надеюсь, я справился.

Leave a comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Предыдущая запись Следующая запись