1632
правки
Изменения
Стек
,rollbackEdits.php mass rollback
== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые в кафетериях, мы должны снять все тарелки выше. Вернемся к описанию операций стека:* <tex> \mathtt{empty} </tex> {{---}} порядок вытаскивания (проверка стека на наличие в нем элементов,* <tex> \mathrm mathtt{poppush} </tex>(запись в стек) тарелок из стопки обратен порядку их в неё помещению ({{---}} операция вставки нового элемента,* <tex> \mathrm mathtt{pushpop} </tex>), и лишь (текущаяснятие со стека) верхняя тарелка может быть извлечена{{---}} операция удаления нового элемента.
==Реализации==
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
===На массиве===
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если <tex>S\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым <tex>(англ. ''empty'')</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <tex> \mathrm mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(англ. ''underflow'')</tex>, что обычно приводит к ошибке. Если значение <tex>S\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется <tex>(англ. ''overflow'')</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
'''boolean''' empty():
'''return''' s.top == 0
'''booleanfunction''' stackEmptypush(S)element : '''if''' S.top == 0 '''return''' 'T''true''' '''else''' '''return''' '''false''' '''function''' push(S, x): Ss.top = Ss.top + 1 Ss[Ss.top] = xelement '''T''' pop(S): '''if''' stackEmptyempty(S)
'''return''' error "underflow"
'''else'''
Как видно из псевдокода выше, все операции со стеком выполняются за <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'''):
'''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
===На списке===
Ключевые поля:* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека. '''function''' push(element: '''T'''): newHead head = ListItem(head, element) head = NewHead
'''T''' pop():
'''return''' data
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же $n$. Стоит заметить, что, хотя общая оценка затрачиваемой памяти $O(n)$, в ней скрыта бóльшая константа, и реализация на списке требует несколько больше памяти.</wikitex> ===На саморасширяющемся массиве===<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <tex> \mathrm mathtt{pushn} </tex> Перед тем. Стоит заметить, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в что стек требует <tex> \mathrm {pop} O(n)</tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации дополнительной памяти на вектореуказатели в списке. '''function''' push(element): '''if''' head == size - 1 newS = new int[size * 2] '''for''' i = 0 '''to''' size newS[i] = S[i] S = newS size = size * 2 head++ S[head] = element '''T''' pop(): temp = head head-- '''if''' head < size / 4 newS = new int[size / 2] '''for''' i = 0 '''to''' size / 4 newS[i] = S[i] S = newS size = size / 2 '''return''' S[temp]</wikitex>
== См. также ==
* [[Персистентный стек]]
== Ссылки Источники информации ==
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
