215
правок
Изменения
Стек
,→На массиве
<wikitex>Для стека с $n$ элементами требуется $O(n)$ памяти, так как она нужна лишь для хранения самих элементов.</wikitex>
===На массиве===
<wikitex>Операция вставки нового элемента применительно к стекам часто называется mathrm\ {$push} $ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.
Если $S.top = 0$, то стек не содержит ни одного элемента и является пустым $(empty)$. Протестировать стек на наличие в нем элементов можно с помощью операции-запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается $(underflow)$, что обычно приводит к ошибке. Если значение $S.top$ больше $n$, то стек переполняется $(overflow)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
