Стек (stack) — это структура данных, представляющая собой специализированным образом организованный список элементов. Доступ к элементам стека осуществляется по принципу LIFO (Last In First Out) — последним пришел, первым вышел. Принцип работы данной структуры данных схож с магазином автоматического огнестрельного оружия. Патроны помещаются в магазин сверху вниз, а используется всегда только верхний патрон. Давайте рассмотрим пример реализации стека на языке C#.

На рисунке ниже представлена схематичная структура стека.

Stack

Stack

У стека есть верхний элемент, с которым и выполняются все три основные манипуляции:

  • Push — добавить новый элемент в стек. При этом этот элемент станет верхним.
  • Pop — удалить верхний элемент из стека сохранив в переменную. При этом верхним станет элемент расположенный ниже удаленного.
  • Peek — прочитать верхний элемент стека, без удаления. При этом верхний элемент останется неизменным.

Теперь приступим к реализации данного класса. Мы будем использовать обобщенный класс. Для хранения данных воспользуемся списком. Данная реализация является весьма примитивной, но позволяет разобраться со структурой и алгоритмом работы данного типа данных.

Стек

using System;
using System.Collections.Generic;
using System.Linq;

namespace Stack
{
    /// <summary>
    /// Стек
    /// </summary>
    /// <typeparam name="T"> Тип данных, хранимых в стеке. </typeparam>
    public class Stack<T>
    {
        /// <summary>
        /// Коллекция хранимых данных.
        /// </summary>
        private List<T> _items = new List<T>();

        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count => _items.Count;

        /// <summary>
        /// Добавить данные в стек.
        /// </summary>
        /// <param name="item"> Добавляемые данные. </param>
        public void Push(T item)
        {
            // Проверяем входные данные на пустоту.
            if(item == null)
            {
                throw new ArgumentNullException(nameof(item));
            }

            // Добавляем данные в коллекцию элементов.
            _items.Add(item);
        }

        /// <summary>
        /// Получить верхний элемент стека с удалением.
        /// </summary>
        /// <returns> Элемент данных. </returns>
        public T Pop()
        {
            // Получаем верхний элемент.
            var item = _items.LastOrDefault();

            // Если элемент пуст, то сообщаем об ошибке.
            if (item == null)
            {
                throw new NullReferenceException("Стек пуст. Нет элементов для получения.");
            }

            // Удаляем последний элемент из коллекции.
            _items.RemoveAt(_items.Count - 1);

            // Возвращаем полученный элемент.
            return item;
        }

        /// <summary>
        /// Прочитать верхний элемент стека без удаления.
        /// </summary>
        /// <returns> Элемент данных. </returns>
        public T Peek()
        {
            // Получаем верхний элемент.
            var item = _items.LastOrDefault();

            // Если элемент пуст, то сообщаем об ошибке.
            if (item == null)
            {
                throw new NullReferenceException("Стек пуст. Нет элементов для получения.");
            }

            return item;
        }
    }
}

Вызов

using System;

namespace Stack
{
    class Program
    {
        static void Main(string[] args)
        {
            // Создаем новый стек.
            var stack = new Stack<int>();

            // Добавляем новые элементы в стек.
            stack.Push(1);
            stack.Push(7);
            stack.Push(42);
            stack.Push(69);
            stack.Push(-17);
            Console.Write($"Стек содержит {stack.Count} элементов.");

            // Получаем элементы с удалением.
            var item1 = stack.Pop();
            Console.WriteLine($"Верхний элемент {item1}.");
            var item2 = stack.Pop();
            Console.WriteLine($"Предпоследний элемент {item2}.");

            // Получаем элемент без удаления.
            stack.Push(88);
            var item3 = stack.Peek();
            Console.WriteLine($"Новый верхний элемент {item3}.");
            var item4 = stack.Peek();
            Console.WriteLine($"Новый верхний элемент {item4}.");

            Console.ReadLine();
        }
    }
}

Заключение

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Stack. Исходный код доступен в репозитории github https://github.com/shwanoff/Stack.

 
×
%d такие блоггеры, как: