Стек на основе массива

Стек представляет собой структуру данных, которая работает по принципу LIFO (Last In First Out - "последний пришел - первый вышел"). Графически стек можно представить в виде столбика или стопки объектов:

Стек имеет вершину, который образует последний добавленный элемент. При добавлении новый элемент помещается поверх вершины стека и образует новую вершину. При удалении удаляется элемент из вершины стека, а предыдущий элемент образует новую вершину.

Так, на приведенном рисунке вначале вершиной стека является "Tom". После добавления нового элемента "Bob" этот элемент располагается поверх элемента "Tom" и становится новой вершиной.

В библиотеке классов .NET в принципе уже есть свой класс, который выполняет роль стека. Это класс - System.Collections.Generic.Stack. Но рассмотрим, как мы сами можем реализовать структуру в виде стека.

Структура стек вне зависимости от языка программирования обладает неким общим функционалом, который составляют метод добавления элемента (как правило, называется push()) и метод извлечения элемента из вершины стека (обычно называется pop()). Кроме того, нередко реализации стеков содержат метод получения элемента из вершины без его извлечения, метод определения размера стека и ряд других.

В начале для реализации структуры данных определим следующий класс:

public class FixedStack<T>
{
    private T[] items; // элементы стека
    private int count;	// количество элементов
	const int n = 10;	// количество элементов в массиве по умолчанию
    public FixedStack()
    {
        items = new T[n];
    }
    public FixedStack(int length)
    {
        items = new T[length];
    }
	// пуст ли стек
    public bool IsEmpty
    {
        get { return count == 0; }
    }
	// размер стека
    public int Count
    {
        get { return count; }
    }
	// добвление элемента
    public void Push(T item)
    {
		// если стек заполнен, выбрасываем исключение
        if (count == items.Length) 
			throw new InvalidOperationException("Переполнение стека");
        items[count++] = item;
    }
	// извлечение элемента
    public T Pop()
    {
        // если стек пуст, выбрасываем исключение
        if (IsEmpty)
            throw new InvalidOperationException("Стек пуст");
        T item = items[--count];
        items[count] = default(T); // сбрасываем ссылку
        return item;
    }
	// возвращаем элемент из верхушки стека
	public T Peek()
    {
		// если стек пуст, выбрасываем исключение
        if (IsEmpty)
            throw new InvalidOperationException("Стек пуст");
        return items[count - 1];
    }
}

Данная реализация представляет обобщенный класс, а поэтому позволяет хранить элементы любого типа. Сами элементы в стеке в реальности будут храниться в массиве items. Для хранения реально добавленного количества элементов в стек служит переменная count.

Для инициализации стека служат два конструктора. Конструктор без параметров создает массив items с длиной 10. Через конструктор с параметром можно самостоятельно установить длину массива.

В методе Push() добавляем элемент в массив, при этом увеличивая значение переменной count. Если же стек (а фактически массив items) уже заполнен, то выбрасываем исключение.

В методе Pop() извлекаем элемент из верхушки стека, при этом уменьшая значение переменной count. Если в стеке нет элементов, то выбрасываем исключение.

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

static void Main(string[] args)
{
	try
    {
		FixedStack<string> stack = new FixedStack<string>(8);
		// добавляем четыре элемента
		stack.Push("Kate");
		stack.Push("Sam");
		stack.Push("Alice");
		stack.Push("Tom");

		// извлекаем один элемент
		var head = stack.Pop();
		Console.WriteLine(head);    // Tom
		
		// просто получаем верхушку стека без извлечения
		head = stack.Peek();
		Console.WriteLine(head);    // Alice
    }
    catch(InvalidOperationException ex)
    {
        Console.WriteLine(ex.Message);
    }
    
	
    Console.Read();
}

Схематично все операции можно выразить следующим образом:

Однако надо отметить, что данный стек имеет один важный недостаток - что если мы вначале не знаем точно, сколько стек может будет содержать элементов - 10, 15, 100, 200...Фиксированная длина массива накладывает ограничение на работу со стеком. Чтобы решить эту проблему, нам надо динамически менять длину массива при увеличении или уменьшении до определенного момента. Так, определим следующий класс стека:

public class Stack<T>
{
    private T[] items;
    private int count;
    const int n = 10;
    public Stack()
    {
        items = new T[n];
    }
    public Stack(int length)
    {
        items = new T[length];
    }

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

    public void Push(T item)
    {
        // увеличиваем стек
        if (count == items.Length)
            Resize(items.Length + 10);

        items[count++] = item;
    }
    public T Pop()
    {
        // если стек пуст, выбрасываем исключение
        if (IsEmpty)
            throw new InvalidOperationException("Стек пуст");
        T item = items[--count];
        items[count] = default(T); // сбрасываем ссылку

        if (count > 0 && count < items.Length - 10)
			Resize(items.Length - 10);

        return item;
    }
    public T Peek()
    {
        return items[count - 1];
    }

    private void Resize(int max)
    {
        T[] tempItems = new T[max];
        for (int i = 0; i < count; i++)
            tempItems[i] = items[i];
        items = tempItems;
    }
}

В данном случае в класс стека по сравнению с предыдущим случаем добавлен метод Resize, который изменяет размер массива до значения max. Для этого в методе просто создается новый массив, в который копируются данные из старого.

Теперь при добавлении в методе Push() больше не надо проверять стек на переполнение. Если вдруг в массиве items больше не окажется места, то мы вызовем функцию Resize, которая увеличит массив на 10 элементов:

// увеличиваем стек
if (count == items.Length)
    Resize(items.Length + 10);

При удалении элемента в методе Pop аналогично изменяем размер, если в массиве items образовалось более 10 пустых ячеек.

Здесь при добавлении и удалении идет изменение количества элементов на 10. Можно увеличивать/уменьшать в два раза и т.д. Однако следует помнить, что изначальное выделение больших объемов памяти увеличит совокупную память, потребляемую приложением. При этом не факт, что хотя бы половина из нее будет использоваться.

В то же время если увеличивать/уменьшать понемногу размер массива, то это увеличит частоту перераспределения памяти, что в конечном счете ведет к уменьшению производительности.

Таким образом, стек стал более гибким в отношении размеров массива, однако сохранил ряд недостатков, связанных с массивами - необходимости перераспределения памяти при добавлении или удалении данных, и увеличим сложность вычислительного алгоритма. И далее мы рассмотрим, как мы можем уйти от этих недостатков.