Theory and Tasks for Students - Spring 2019
Stack

Stack - структура данных, также называемая LIFO - Last In, First Out. Вообще "stack" в переводе с английского - стопка, чем по принципу работы эта структура и является - в стопке можно взаимодействовать только с верхним элементом: добавить один, убрать один и посмотреть на верхний элемент. Таким образом, тип, реализующий стек, обычно имеет три метода:

  • void Push(item) добавляет один элемент,
  • type Pop() удаляет верхний элемент и возвращает его значение,
  • type Top() возвращает значение верхнего элемента, не производя изменений.

В качестве хранилища данных внутри стека используется обычный массив, также можно использовать vector (List в C#), однако это усложняет структуру без необходимости. Размер стека обычно ограничен либо константой внутри типа, либо аргументом конструктора. В некоторых реализациях, как и в типе vector максимальный размер стека увеличивается при необходимости для избежания переполнения.

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

Классическая реализация стека чисел: class Stack { private int[] _items; private int _top = -1; public bool IsEmpty { get { return _top == -1; } } public int Capacity { get { return _items.Length; } } public Stack() : this(512) { } public Stack(int capacity) { _items = new int[capacity]; } public void Push(int item) { if (_top + 1 >= _items.Length) { throw new StackOverflowException(String.Format("Stack size exceeded maximum capacity of {0} elements.", _items.Length)); } _items[++_top] = item; } public int Pop() { if (_top < 0) { throw new StackOverflowException(String.Format("Can't remove elements from an empty Stack")); } return _items[_top--]; } public int Top() { if (_top < 0) { throw new StackOverflowException(String.Format("No top element in an empty Stack")); } return _items[_top]; } }