1632
правки
Изменения
Стек
,rollbackEdits.php mass rollback
== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack — '' {{---}} стопка) — динамическая {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — {{---}} первым вышел» (last-in, first-out — {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые мы должны снять все тарелки выше. Вернемся к описанию операций стека:* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в кафетерияхнем элементов, - порядок вытаскивания * <tex> \mathtt{push} </tex> (pop) тарелок из стопки обратен порядку их запись в неё помещению (pushстек){{---}} операция вставки нового элемента, и лишь * <tex> \mathtt{pop} </tex> (текущаяснятие со стека) верхняя тарелка может быть извлечена{{---}} операция удаления нового элемента.
==Реализация на массивеРеализации==Для стека с <wikitextex>Операция вставки нового элемента применительно к стекам часто называется $push$ n</tex> элементами требуется <tex>O(запись в стекn)</tex> памяти, а операция удаления — $pop$ (снятие со так как она нужна лишь для хранения самих элементов.===На массиве===Перед реализацией стека). Стеквыделим ключевые поля:* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более $<tex>n$ </tex> элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S* <tex>\mathtt{s.top$, представляющим собой }</tex> {{---}} индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если $S<tex>\mathtt{s.top = 0$}</tex>, то стек не содержит ни одного элемента и является пустым $(англ. ''empty'')$. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}} запроса $Stack$_$Empty$<tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается $(англ. ''underflow'')$, что обычно приводит к ошибке. Если значение $S<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]
'''T''' pop(): data =head.data head =Реализация на списке==head.next<wikitex>Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции $push$ будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью $pop$ будет текущая голова. После вызова функции $push$ текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции $pop$ будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой. '''return''' data
== См. также ==
* [[Очередь]]
* [[Персистентный стек]]
== Ссылки Источники информации ==*Википедия**[http[wikipedia://ru.wikipedia.org/wiki/:Стек |Википедия {{---}} Стек]]
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1