Стек

Определение

Стек

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

Реализации

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

На массиве

<wikitex>Операция вставки нового элемента применительно к стекам часто называется [math] \mathrm {push} [/math] (запись в стек), а операция удаления — [math] \mathrm {pop} [/math] (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.

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

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

boolean stackEmpty(S):
  if S.top == 0
    return true
  else
    return false

function push(S, x):
  S.top = S.top + 1
  S[S.top] = x

integer pop(S):
  if stackEmpty(S)
    return error "underflow"
  else 
    S.top = S.top - 1
    return S[S.top + 1]

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

На списке

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

function push(element):
  OldHead = new ListItem
  NewHead = new ListItem
  OldHead = head
  NewHead.data = element
  NewHead.next = OldHead
  head = NewHead
  delete NewHead

integer pop():
  OldHead = new ListItem
  OldHead = head
  int element = OldHead.data
  head = OldHead.next
  delete OldHead
  return element

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

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

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

function push(e):
  if n == s - 1
    w = new int[s * 2]
    for i = 0 to s
      w[i] = v[i]
    delete v
    v = w
    s = s * 2
  n++
  v[n] = e

integer pop():
  r = n
  n--
  if n < size / 4
    w = new int[size / 2]
    for i = 0 to size / 4
      w[i] = v[i]
    delete v
    v = w
    size  = size / 2
  return v[r]

</wikitex>

См. также

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

Ссылки

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