1632
правки
Изменения
Стек
,rollbackEdits.php mass rollback
== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
'''T''' pop(): '''if''' empty() '''return''' error "underflow" '''else''' s.top = s.top - 1 '''return''' s[s.top + 1] Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>. ==Графическое представление=На саморасширяющемся массиве===Возможна реализация стека на [[ФайлСаморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: lifoпри операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения. Создадим вектор и определим операции стека на нём.pngВ функции <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'''): '''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 ===На списке===Стек можно реализовать и на [[Список |trumb|300px|Простое представление стекасписке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <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*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1* [http://rucomp-science.wikipedianarod.orgru/wikiProgr/СтекStack.htm Динамические структуры данных: стеки][[Категория:Дискретная математика и алгоритмы]][[Категория:Амортизационный анализ]][[Категория:Структуры данных]]
