143
правки
Изменения
Стек
,Нет описания правки
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.
Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
===На саморасширяющемся массиве===
Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <tex> \mathrm mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathrm mathtt {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
Ключевые поля:
