Стек
Определение
Стек (англ. stack — стопка) — структура данных, представляющая собой динамическое множество с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкивание (pop), возможно также только из вершины стека, при этом, второй сверху элемент становится верхним.
Стеки широко применяются в вычислительной технике — в частности, для отслеживания точек возврата из подпрограмм используется стек вызовов, который является неотъемлемой частью архитектуры большинства современных процессоров. Язык программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедур.
Арифметические сопроцессоры, программируемые микрокалькуляторы используют стековую модель вычислений.
Работа стека
<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
