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

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

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

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

/// <summary>
/// Простой пример реализации структуры данных стек нативными средствами языка C#.
/// </summary>
/// <typeparam name="T">Тип хранимой информации</typeparam>
public class Stack<T>
{
	private readonly int _Size;
	private readonly T[] _Array;
	private int _Top;
}

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

/// <summary>
/// Конструктор. Создаём стек
/// </summary>
/// <param name="Size">Размер стека</param>
public Stack(int Size)
{
	this._Size = Size;
	this._Top = 0;
	this._Array = new T[this._Size];
}

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

/// <summary>
/// Маркер верхнего элемента стека
/// </summary>
public int Top
{
	get
	{
		return this._Top;
	}
}

/// <summary>
/// Размер стека
/// </summary>
public int Size
{
	get
	{
		return this._Size;
	}
}

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

/// <summary>
/// Количество элементов стека
/// </summary>
public int Count
{
	get
	{
		return this._Top;
	}
}

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

/// <summary>
/// Проверить заполнен ли стек
/// </summary>
/// <returns></returns>
public bool IsFull()
{
	return this._Top == this._Size;
}

/// <summary>
/// Проверить пустой ли стек
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
	return this._Top == 0;
}

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

/// <summary>
/// Добавляем элемент в стек
/// </summary>
/// <param name="Element">Элемент</param>
public void Push(T Element)
{
	if (this.IsFull())
		throw new Exception();

	this._Array[this._Top++] = Element;
}

/// <summary>
/// Вернуть верхний элемент
/// </summary>
/// <returns>Элемент</returns>
public T Peek()
{
	return this._Array[this._Top - 1];
}

/// <summary>
/// Считывание из стека верхнего элемента
/// </summary>
/// <returns>Элемент</returns>
public T Pop()
{
	return this._Array[--this._Top];
}

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

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

public IEnumerator<T> GetEnumerator()
{
	if (this.IsEmpty())
		throw new Exception("Стек не заполнен.");

	for (int i = this._Top; i > 0; i--)
		yield return _Array[i - 1];
}

IEnumerator IEnumerable.GetEnumerator()
{
	return this.GetEnumerator();
}

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

class Program
{
	static void Main(string[] args)
	{
		Console.Title = "Custom simple Stack in native C#";

		Stack<string> s = new Stack<string>(5);
		Console.WriteLine("Добавляем на склад коробки: 1, 2, 3...");
		s.Push("первая коробка");
		s.Push("вторая коробка");
		s.Push("третья коробка");
		Console.WriteLine("Всего коробок: " + s.Count.ToString());
		Console.WriteLine();

		Console.WriteLine("Достаём крайнюю коробку: " + s.Pop());
		Console.WriteLine("Достаём крайнюю коробку: " + s.Pop());
		Console.WriteLine("Узнать какая коробка осталась: " + s.Peek());
		Console.WriteLine("Всего коробок: " + s.Count.ToString());
		Console.WriteLine();

		Console.WriteLine("Добавим ещё коробки: 4, 5...");
		s.Push("четвертая коробка");
		s.Push("пятая коробка");
		Console.WriteLine("Всего коробок: " + s.Count.ToString());
		Console.WriteLine();

		Console.WriteLine("Переберём оставшиеся коробки на складе:");
		foreach(string box in s)
		{
			Console.WriteLine('-' + box);
		}
		Console.Read();
	}
}

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

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