Изменения

'''Стек''' (от англ. stack {{---}} стопка) — {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — {{---}} первым вышел» (last{{---}}in, first{{---}}out — {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях, {{--- }} порядок вытаскивания (<math> \mathrm {pop} </math>) тарелок из стопки обратен порядку их в неё помещению (<math> \mathrm {push} </math>), и лишь (текущая) верхняя тарелка может быть извлечена.

<wikitex>Операция вставки нового элемента применительно к стекам часто называется <math> \mathrm {push} </math> (запись в стек), а операция удаления — {{---}} <math> \mathrm {pop} </math> (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — {{---}} элемент на дне стека, а $S[S.top]$ — {{---}} элемент на его вершине.

Если $S.top = 0$, то стек не содержит ни одного элемента и является пустым $(empty)$. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <math> \mathrm {stackEmpty} </math>. Если элемент снимается с пустого стека, говорят, что он опустошается $(underflow)$, что обычно приводит к ошибке. Если значение $S.top$ больше $n$, то стек переполняется $(overflow)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <math> \mathrm {push} </math> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <math> \mathrm {pop} </math>, перед тем, как изъять элемент из массива, — {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.