285
правок
Изменения
Стек
,→Работа стека
==Работа стека==
<wikitex>[[Файл: lifo.png|trumbthumb|300pxright|Простое представление 200px|Стек]]Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $top[S]$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..top [S]]$, где $S[1]$ — элемент на дне стека, а $S[top[S]]$ — элемент на его вершине. Если $top[S] = 0$, то стек не содержит ни одного элемента и является пустым (empty). Протестировать стек на наличие в нем элементов можно с помощью операции-запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается ($underflow$), что обычно приводит к ошибке. Если значение $top[S]$ больше $n$, то стек переполняется ($overflow$). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.) Каждую операцию над стеком можно легко реализовать несколькими строками кода: Stack_Empty(S) { if top[S]=0 return true; else return false; } push(S,x) { top[S]$\leftarrow$ top[S] - 1; S[top[S]] $\leftarrow$ x; } pop(S) { if Stack_Empty(S) return error "underflow"; else { top[S] $\leftarrow$ top[S] - 1; return S[top[S] + 1]; } Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.</wikitex>
== См. также ==
* [[Очередь]]
