Стек

Определение

Стек

Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях — порядок вытаскивания тарелок из стопки обратен порядку их в неё помещению, и лишь (текущая) верхняя тарелка может быть извлечена.

• [math] \mathrm {empty} [/math] — проверка стека на наличие в нем элементов
• [math] \mathrm {push} [/math] (запись в стек) — операция вставки нового элемента
• [math] \mathrm {pop} [/math] (снятие со стека) — операция удаления нового элемента

Реализации

Для стека с [math]n[/math] элементами требуется [math]O(n)[/math] памяти, так как она нужна лишь для хранения самих элементов.

На массиве

Перед реализацией стека выделим ключевые поля:

• [math]s [1..n][/math] — массив, с помощью которого реализуется стек, способный вместить не более [math]n[/math] элементов
• [math]s.top[/math] — индекс последнего помещенного в стек элемента

Стек состоит из элементов [math]s[1..s.top][/math], где [math]s[1][/math] — элемент на дне стека, а [math]s[s.top][/math] — элемент на его вершине. Если [math]s.top = 0[/math], то стек не содержит ни одного элемента и является пустым [math](empty)[/math]. Протестировать стек на наличие в нем элементов можно с помощью операции — запроса [math] \mathrm {stackEmpty} [/math]. Если элемент снимается с пустого стека, говорят, что он опустошается [math](underflow)[/math], что обычно приводит к ошибке. Если значение [math]s.top[/math] больше [math]n[/math], то стек переполняется [math](overflow)[/math]. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

Каждую операцию над стеком можно легко реализовать несколькими строками кода:

boolean stackEmpty(s : stack<T>):
  return s.top == 0

function push(s : stack<T>, element : T):
  s.top = s.top + 1
  s[s.top] = element

T pop(s : stack<T>):
  if stackEmpty(s)
    return error "underflow"
  else 
    s.top = s.top - 1
    return s[s.top + 1]

Как видно из псевдокода выше, все операции со стеком выполняются за [math]O(1)[/math].

На списке

Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции [math] \mathrm {push} [/math] будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью [math] \mathrm {pop} [/math] будет текущая голова. После вызова функции [math] \mathrm {push} [/math] текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции [math] \mathrm {pop} [/math] будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

Заведем конструктор вида ListItem(next : ListItem, data : T)

Ключевые поля:

• [math]head.data[/math] — значение в верхушке стека
• [math]head.next[/math] — значение следующее за верхушкой стека

function push(element : T):
  newHead = ListItem(head, element)
  head = newHead

T pop():
  data = head.data
  head = head.next
  return data

В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же [math]n[/math]. Стоит заметить, что, хотя общая оценка затрачиваемой памяти [math]O(n)[/math], в ней скрыта бóльшая константа из-за того, что все элементы лежат в памяти не подряд, и реализация на списке требует несколько больше памяти.

На саморасширяющемся массиве

Возможна реализация стека на векторе. Для этого нужно создать вектор и определить операции стека на нём. В функции [math] \mathrm {push} [/math] Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в [math] \mathrm {pop} [/math], перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

Ключевые поля:

• [math]s[0..n-1][/math] — старый массив, в котором хранится стек
• [math]newStack[0..newSize][/math] — новый массив, в котором хранится стек
• [math]head[/math] — верхушка стека
• [math]capacity[/math] — размер стека

function push(element : T):
  if head == capacity - 1
    T newStack[capacity * 2]
    for i = 0 to capacity - 1
      newStack[i] = s[i]
    s = newStack
    capacity = capacity * 2
  head++
  s[head] = element

T pop():
  temp = head
  head--
  if head < capacity / 4
    T newStack[capacity / 2]
    for i = 0 to capacity / 4 - 1
      newStack[i] = s[i]
    s = newStack
    capacity = capacity / 2
  return s[temp]

См. также

• Очередь
• Персистентный стек

Ссылки

• Википедия — Стек
• Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
• T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
• Динамические структуры данных: стеки