Изменения

Перейти к: навигация, поиск

Стек

12 байт добавлено, 17:53, 10 июля 2019
м
Поправка пунктуации.
== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые в кафетериях {{---}} порядок вытаскивания тарелок из стопки обратен порядку их в неё помещению, и лишь (текущая) верхняя тарелка может быть извлеченамы должны снять все тарелки выше.Вернемся к описанию операций стека:* <tex> \mathrm mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,* <tex> \mathrm mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,* <tex> \mathrm mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
==Реализации==
===На массиве===
Перед реализацией стека выделим ключевые поля:
* <tex>\mathtt{s [1..\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.
Стек состоит из элементов <tex>\mathtt {s[1..\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым <tex>(англ. ''empty'')</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathrm mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(англ. ''underflow'')</tex>, что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется <tex>(англ. ''overflow'')</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
'''boolean''' stackEmptyempty(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''' stackEmptyempty(s)
'''return''' error "underflow"
'''else'''
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
===На спискесаморасширяющемся массиве===Стек можно реализовать и Возможна реализация стека на [[Список Саморасширяющийся_массив| спискединамическом массиве]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm {push} </tex> будут перед головой, сами в результате чего появляется существенное преимущество над обычной реализацией: при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {операции push} </tex> текущая голова уже станет старой и будет являться следующим элементом мы никогда не сможем выйти за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm {pop} </tex> будет получена и возвращена информацияграницы массива, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головойтем самым избежим ошибки исполнения.
Заведем конструктор вида Создадим вектор и определим операции стека на нём. В функции <codetex>ListItem(next : '''ListItem'''\mathtt {push} </tex> Перед тем, как добавить новый элемент, data : '''T''')будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </codetex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
Ключевые поля:
* <tex>head.data</tex> {{---}} значение в верхушке стека* <tex>head.next</tex> {{---}} значение следующее за верхушкой стека  '''function''' push(element : '''T'''): newHead = ListItem(head, element) head = newHead  '''T''' pop(): data = head.data head = head.next '''return''' data В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>n</tex>. Стоит заметить, что, хотя общая оценка затрачиваемой памяти <tex>O(n)</tex>, в ней скрыта бóльшая константа из-за того, что все элементы лежат в памяти не подряд, и реализация на списке требует несколько больше памяти. ===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <tex> \mathrm {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathrm {pop} </tex>, перед тем, как изъять элемент из массива, {mathtt{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе. Ключевые поля:* <tex>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'''):
'''T''' pop():
temp = s[head]
head--
'''if''' head < capacity / 4
s = newStack
capacity = capacity / 2
'''return''' stemp ===На списке===Стек можно реализовать и на [[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)  '''T''' pop(): data = head.data head = head.next '''return''' data В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
== См. также ==
* [[Персистентный стек]]
== Ссылки Источники информации ==
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
13
правок

Навигация