Изменения
Стек
,→Реализации
===На массиве===
Перед реализацией стека выделим ключевые поля:
* <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>O(1)</tex>.
===На саморасширяющемся массиве===
Ключевые поля:
* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек,* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования.
* <tex>\mathtt{head}</tex> {{---}} верхушка стека
* <tex>\mathtt{capacity}</tex> {{---}} размер массива
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> дополнительной памяти на указатели в списке.
== См. также ==
