Стек (Stack). C# Реализация на массиве.

Стек - динамическая структура данных, которая работает по принципу "Последним вошел - первым вышел". По английски LIFO (last-in, first-out).
Графическое представление стека:

Как можно видеть мы добавляем один элемент с помощью метода Push, и потом с помощью метода Pop мы его вытаскиваем.
Жизненный пример: Стопка тарелок, допустим для того чтобы накрыть на стол нам надо 3 тарелки, мы будем с вершины брать по одной тарелке, т.е. 3 раза вызовем метод S.Pop(). То есть, для того, чтобы снять n-3 тарелку, мы должны сначала снять n, n-1, n-2 тарелки.
Применение:

• Стек можно использовать для того, чтобы избавится от рекурсии, так идея вызова рекурсивных функций сама использует стек. Адрес возврата и локальные переменные рекурсивной функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Единственный минус такого использования в том, что очень хорошо отъедает память :D, поэтому надо избегать программ, которая допускает большой глубины рекурсии.
• Стек используется при парсинге HTML/XML деревьев.
• Существует стек вызовов (call stack), в который заносится информация о возврате из функции. Например при вызове функции A() из функции main, в стек вызовов заносится адрес возврата, то есть адрес следующей функции, в которую должно передатся управление, например у нас функция (не рекурсивна) A() {return 0;}, то адрес возврата у нас будет адрес функции main(). К тому же заносится информация о локальных переменных и значения параметров функции.
• Например, у нас есть функция main из нее вызывается функция A(), из A() вызывается B(), то стек у нас будет вот такой: Head-> [B(),A(),main()]. B()-вершина стека, ниже будет А(), и на дне стека main(). При возврате из B() управление передастся к A(), при возврате из A() управление передастся к main().
• Также стек используется в калькуляторе. Например вот из этого:
• Input: (((8 + 1) - (7 - 4)) / (11 - 9))  Превратили в вот это с помощью стека (из инфиксной в обратную польскую)
  Output: 8 1 + 7 4 - - 11 9 - /
  
  

В C# внутреннее устройство класса стека основано на использовании массива, что меня очень удивило, так как реализация на массивах не очень оптимальна в плане выделения памяти.
В своей реализации я сделаю только самые базовые метода без Enumerator'а и других интересных фичей, поэтому, увы, foreach к моему стеку не работает. :(
UML диаграмма:

Реализация:

public class CStack< T>
    {
        private T []_array; //массив для хранения данных типа T
        private const int defaultCapacity=10; //вместимость по умолчанию, потом можно расширить
        private int size; //размер

        public CStack(){ //конструктор
            this.size=0;
            this._array=new T [defaultCapacity];
        }

        public bool isEmpty() //проверка на пустоту
        {
            return this.size == 0;
        }

        public virtual int Count //параметр для вывода размера 
        {
            get
            {
                return this.size;
            }
        }

        public T Pop() //метод взятия с вершины
        {
            if (this.size == 0)
            { //вброс ошибки при взятии с пустого стека (Overflow)
                throw new InvalidOperationException();
            }
            return this._array[--this.size];
        }

        public void Push(T newElement)
        {
            if (this.size == this._array.Length) //если у нас переполнение...
            { //знаю, что неоптимально, но это c#...
                T[] newArray = new T[2 * this._array.Length];
                Array.Copy(this._array, 0, newArray, 0, this.size);
                this._array = newArray; //просто создаем новый массив с двойным размером
            } 
            this._array[this.size++] = newElement; //вставляем элемент
        }

        public T Peek()
        {
            if (this.size == 0)
            {
                throw new InvalidOperationException();
            }
            return this._array[this.size - 1];
        }
    }

Демонстрация работы:

CStack stack = new CStack();
            stack.Push(3);
            stack.Push(18);
            Console.WriteLine("element Number "+stack.Count.ToString()+" is "+stack.Pop().ToString());
            Console.WriteLine("element Number " + stack.Count.ToString() + " is " + stack.Pop().ToString());
            Console.ReadLine();

Posted in: Алгоритмы, Структуры данных, C#