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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показано 155 промежуточных версий 11 участников)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 +
[[Файл: lifo.png|thumb|right|200px|Стек]]
 +
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
 +
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,
 +
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,
 +
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
  
'''Стек''' (англ. stack — стопка) — структура данных, представляющая собой динамическое множество с методом доступа к элементам ''LIFO'' (англ. Last In — First Out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
+
==Реализации==
 +
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
 +
===На массиве===
 +
Перед реализацией стека выделим ключевые поля:
 +
* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,
 +
* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.
  
Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху).
+
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.
Удаление элемента, называемое также выталкивание (pop), возможно также только из вершины стека, при этом, второй сверху элемент становится верхним.
+
Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
  
Стеки широко применяются в вычислительной технике — в частности, для отслеживания точек возврата из подпрограмм используется стек вызовов, который является неотъемлемой частью архитектуры большинства современных процессоров. Язык программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедур.
+
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 +
 +
'''boolean''' empty():
 +
  '''return''' s.top == 0
 +
 
 +
'''function''' push(element : '''T'''):
 +
  s.top = s.top + 1
 +
  s[s.top] = element
 +
 
 +
'''T''' pop():
 +
  '''if''' empty()
 +
    '''return''' error "underflow"
 +
  '''else'''
 +
    s.top = s.top - 1
 +
    '''return''' s[s.top + 1]
 +
 
 +
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
 +
 
 +
===На саморасширяющемся массиве===
 +
Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.
 +
 
 +
Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
  
Арифметические сопроцессоры, программируемые микрокалькуляторы используют стековую модель вычислений.
+
Ключевые поля:
 +
* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек,
 +
* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
 +
* <tex>\mathtt{head}</tex> {{---}} верхушка стека,
 +
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
  
==Работа стека==
+
'''function''' push(element : '''T'''):
<wikitex>
+
  '''if''' head == capacity - 1
[[Файл: lifo.png|thumb|right|200px|Стек]]Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $top[S]$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..top [S]]$, где $S[1]$ — элемент на дне стека, а $S[top[S]]$ — элемент на его вершине.
+
    '''T''' newStack[capacity * 2]
 +
    '''for''' i = 0 '''to''' capacity - 1
 +
      newStack[i] = s[i]
 +
    s = newStack
 +
    capacity = capacity * 2
 +
  head++
 +
  s[head] = element
  
Если $top[S] = 0$, то стек не содержит ни одного элемента и является пустым (empty). Протестировать стек на наличие в нем элементов можно с помощью операции-запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается ($underflow$), что обычно приводит к ошибке. Если значение $top[S]$ больше $n$, то стек переполняется ($overflow$). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
+
'''T''' pop():
 +
  temp = s[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''' temp
  
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
+
===На списке===
 +
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
 +
 
 +
Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code>
 +
 
 +
Ключевые поля:
 +
* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,
 +
* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека.
 +
 
 +
'''function''' push(element : '''T'''):
 +
  head = ListItem(head, element)
  
  Stack_Empty(S)
+
  '''T''' pop():
{
+
  data = head.data
if top[S]=0
+
  head = head.next
    return true;
+
  '''return''' data
else
 
    return false;
 
}
 
push(S,x)
 
{
 
top[S] $\leftarrow$ top[S] - 1;
 
S[top[S]] $\leftarrow$ x;
 
}
 
pop(S)
 
{
 
if Stack_Empty(S)
 
    return error "underflow";
 
else
 
{
 
    top[S] $\leftarrow$ top[S] - 1;
 
    return S[top[S] + 1];
 
}
 
  
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.
+
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
</wikitex>
 
  
 
== См. также ==
 
== См. также ==
Строка 47: Строка 89:
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
  
== Ссылки ==
+
== Источники информации ==
*Википедия
+
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
**[http://ru.wikipedia.org/wiki/Стек Стек]
 
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
 +
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
 +
* [http://comp-science.narod.ru/Progr/Stack.htm Динамические структуры данных: стеки]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Амортизационный анализ]]
 
[[Категория:Амортизационный анализ]]
 +
[[Категория:Структуры данных]]

Текущая версия на 19:07, 4 сентября 2022

Определение

Стек

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

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

Реализации

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

На массиве

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

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

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

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

boolean empty():
  return s.top == 0
function push(element : T):
  s.top = s.top + 1
  s[s.top] = element
T pop():
  if empty()
    return error "underflow"
  else 
    s.top = s.top - 1
    return s[s.top + 1]

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

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

Возможна реализация стека на динамическом массиве, в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.

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

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

  • [math]\mathtt{s[0\dots n-1]}[/math] — старый массив, в котором хранится стек,
  • [math]\mathtt{newStack[0\dots newSize]}[/math] — временный массив, где хранятся элементы после перекопирования,
  • [math]\mathtt{head}[/math] — верхушка стека,
  • [math]\mathtt{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 = s[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 temp

На списке

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

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

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

  • [math]\mathtt{head.data}[/math] — значение в верхушке стека,
  • [math]\mathtt{head.next}[/math] — значение следующее за верхушкой стека.
function push(element : T):
  head = ListItem(head, element)
T pop():
  data = head.data
  head = head.next
  return data

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

См. также

Источники информации