Изменения

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

Стек

58 байт добавлено, 17:53, 10 июля 2019
м
Поправка пунктуации.
== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые в кафетериях {{---}} порядок вытаскивания тарелок из стопки обратен порядку их в неё помещению, и лишь (текущая) верхняя тарелка может быть извлеченамы должны снять все тарелки выше.Вернемся к описанию операций стека:* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,* <tex> \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> {{---}} элемент на его вершине.
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
'''boolean''' stackEmptyempty():
'''return''' s.top == 0
'''T''' pop():
'''if''' stackEmptyempty()
'''return''' error "underflow"
'''else'''
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
===На спискесаморасширяющемся массиве===Стек можно реализовать и Возможна реализация стека на [[Список Саморасширяющийся_массив| спискединамическом массиве]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <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> дополнительной памяти на указатели в списке. ===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]]. Для этого нужно создать Создадим вектор и определить определим операции стека на нём. В функции <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'''):
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)
 
'''T''' pop():
data = head.data
head = head.next
'''return''' data
 
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
== См. также ==
13
правок

Навигация