Стек
Определение
Стек (от англ. stack - стопка) — это динамическое множество, добавление и удаление элементов в котором происходит путём операций Push и Pop соответственно. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок используемые в кафетериях - порядок вытаскивания (pop) тарелок из стопки обратен порядку их в неё помещению (push), и лишь (текущая) верхняя тарелка может быть извлечена.
Реализация на массиве
<wikitex>Операция вставки нового элемента применительно к стекам часто называется $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)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
Stack_Empty(S)
{
if S.top == 0
return true;
else
return false;
}
push(S,x)
{
S.top = S.top + 1;
S[S.top] = x;
}
pop(S)
{
if Stack_Empty(S)
return error "underflow";
else
{
S.top = S.top - 1;
return S[S.top + 1];
}
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.</wikitex>
См. также
Ссылки
- Википедия
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
