Стек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(На массиве)
Строка 6: Строка 6:
 
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
 
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
 
===На массиве===
 
===На массиве===
Операция вставки нового элемента применительно к стекам часто называется <tex> \mathrm {push} </tex> (запись в стек), а операция удаления {{---}} <tex> \mathrm {pop} </tex> (снятие со стека). Стек, способный вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>S [1..n]</tex>. Этот массив обладает атрибутом <tex>S.top</tex>, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов <tex>S[1..S.top]</tex>, где <tex>S[1]</tex> {{---}} элемент на дне стека, а <tex>S[S.top]</tex> {{---}} элемент на его вершине.  
+
Операция вставки нового элемента применительно к стекам часто называется <tex> \mathrm {push} </tex> (запись в стек), а операция удаления {{---}} <tex> \mathrm {pop} </tex> (снятие со стека). Стек, способный вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>s [1..n]</tex>. Этот массив обладает атрибутом <tex>s.top</tex>, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов <tex>s[1..s.top]</tex>, где <tex>s[1]</tex> {{---}} элемент на дне стека, а <tex>s[s.top]</tex> {{---}} элемент на его вершине.  
  
Если <tex>S.top = 0</tex>, то стек не содержит ни одного элемента и является пустым <tex>(empty)</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <tex> \mathrm {stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(underflow)</tex>, что обычно приводит к ошибке. Если значение <tex>S.top</tex> больше <tex>n</tex>, то стек переполняется <tex>(overflow)</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
+
Если <tex>s.top = 0</tex>, то стек не содержит ни одного элемента и является пустым <tex>(empty)</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <tex> \mathrm {stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(underflow)</tex>, что обычно приводит к ошибке. Если значение <tex>s.top</tex> больше <tex>n</tex>, то стек переполняется <tex>(overflow)</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
  
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
  
  '''boolean''' stackEmpty(S):
+
  '''boolean''' stackEmpty(s):
   '''if''' S.top == 0
+
   '''if''' s.top == 0
 
     '''return''' '''true'''
 
     '''return''' '''true'''
 
   '''else'''
 
   '''else'''
 
     '''return''' '''false'''
 
     '''return''' '''false'''
 
   
 
   
  '''function''' push(S, x):
+
  '''function''' push(s, x):
   S.top = S.top + 1
+
   s.top = s.top + 1
   S[S.top] = x
+
   s[s.top] = x
 
   
 
   
  '''T''' pop(S):
+
  '''T''' pop(s):
   '''if''' stackEmpty(S)
+
   '''if''' stackEmpty(s)
 
     '''return''' error "underflow"
 
     '''return''' error "underflow"
 
   '''else'''  
 
   '''else'''  
     S.top = S.top - 1
+
     s.top = s.top - 1
     '''return''' S[S.top + 1]
+
     '''return''' s[s.top + 1]
  
 
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
 
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
 +
 
===На списке===
 
===На списке===
 
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm {push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm {pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
 
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm {push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm {pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

Версия 15:38, 12 июня 2014

Определение

Стек

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

Реализации

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

На массиве

Операция вставки нового элемента применительно к стекам часто называется [math] \mathrm {push} [/math] (запись в стек), а операция удаления — [math] \mathrm {pop} [/math] (снятие со стека). Стек, способный вместить не более [math]n[/math] элементов, можно реализовать с помощью массива [math]s [1..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):
  if s.top == 0
    return true
  else
    return false

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

T pop(s):
  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(ListItem next, T data)

function push(element):
  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], перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

function push(element):
  if head == size - 1
    newS = new int[size * 2]
    for i = 0 to size
      newS[i] = S[i]
    S = newS
    size = size * 2
  head++
  S[head] = element
T pop():
  temp = head
  head--
  if head < size / 4
    newS = new int[size / 2]
    for i = 0 to size / 4
      newS[i] = S[i]
    S = newS
    size  = size / 2
  return S[temp]

См. также

Ссылки