Стек

В прошлой теме была реализована структура Стек на основе массивов. Однако в подобной структуре мы сталкиваемся с необходимостью динамически изменять размер массива, выделяя для него новую память, или, наоборот, уменьшая ее. Альтернативой является создание стека на основе односвязного списка. Структура "Односвязный список" является простой и понятной и в то же время достаточно эффективной для создания других структур данных.

Каждый элемент в стеке, как и в односвязном списке, будет представлен классом Node:

public class Node<T>
{
    public Node(T data)
    {
        Data = data;
    }
    public T Data { get; set; }
    public Node<T> Next { get; set; }
}

На основе класса Node мы можем реализовать структуру стек:

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

namespace SimpleAlgorithmsApp
{
    public class NodeStack<T> : IEnumerable<T>
    {
        Node<T> head;
        int count;

        public bool IsEmpty
        {
            get { return count == 0; }
        }
        public int Count
        {
            get { return count; }
        }

        public void Push(T item)
        {
            // увеличиваем стек
            Node<T> node = new Node<T>(item);
            node.Next = head; // переустанавливаем верхушку стека на новый элемент
            head = node;
            count++;
        }
        public T Pop()
        {
            // если стек пуст, выбрасываем исключение
            if (IsEmpty)
                throw new InvalidOperationException("Стек пуст");
            Node<T> temp = head;
            head = head.Next; // переустанавливаем верхушку стека на следующий элемент
            count--;
            return temp.Data;
        }
        public T Peek()
        {
            if (IsEmpty)
                throw new InvalidOperationException("Стек пуст");
            return head.Data;
        }

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

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            Node<T> current = head;
            while (current != null)
            {
                yield return current.Data;
                current = current.Next;
            }
        }
    }
}

В отличие от предыдущей реализации стека, построенной на массивах, здесь мы уже уходим от ограничения, которые накладывали массивы - нам не надо пересоздавать массив при добавление в него или удалении из него данных. Нам достаточно переустановить ссылку на элемент head, который является верхушкой стека. При этом алгоритмическая сложность обоих методов Push и Pop составляет O(1).

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

Применение стека:

NodeStack<string> stack = new NodeStack<string>();
stack.Push("Tom");
stack.Push("Alice");
stack.Push("Bob");
stack.Push("Kate");

foreach (var item in stack)
{
    Console.WriteLine(item);
}
Console.WriteLine();
string header = stack.Peek();
Console.WriteLine($"Верхушка стека: {header}");
Console.WriteLine();

header = stack.Pop();
foreach (var item in stack)
{
    Console.WriteLine(item);
}

Консольный вывод:

Kate
Bob
Alice
Tom

Верхушка стека: Kate

Bob
Alice
Tom