285
правок
Изменения
Стек
,→Реализации
==Реализации==
<wikitex>Для стека с $n$ элементами требуется $O(n)$ памяти, так как она нужна лишь для хранения самих элементов.</wikitex>
===На массиве===
<wikitex>Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.
return S[S.top + 1]
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.</wikitex>
===На списке===
head = head->next
return element
Здесь видно, что, кроме самих данных, используются указатели на следующие элементы, которых столько же, сколько и элементов.
</wikitex>
