143
правки
Изменения
Стек
,Нет описания правки
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях {{---}} порядок вытаскивания тарелок из стопки обратен порядку их в неё помещению, и лишь (текущая) верхняя тарелка может быть извлечена.
* <tex> \mathrm mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов* <tex> \mathrm mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента* <tex> \mathrm mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента
==Реализации==
===На массиве===
Перед реализацией стека выделим ключевые поля:
* <tex>\mathrm mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов* <tex>\mathrm mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента
Стек состоит из элементов <tex>\mathrm mathtt {s[1\dots s.top]}</tex>, где <tex>\mathrmmathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathrmmathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если <tex>s.top = 0</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathrm mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathrmmathtt{s.top}</tex> больше <tex>\mathrmmathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
===На списке===
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code>
Ключевые поля:
* <tex>\mathrmmathtt{head.data}</tex> {{---}} значение в верхушке стека* <tex>\mathrmmathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека
'''function''' push(element : '''T'''):
Ключевые поля:
* <tex>\mathrmmathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек* <tex>\mathrmmathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования* <tex>\mathrmmathtt{head}</tex> {{---}} верхушка стека* <tex>\mathrmmathtt{capacity}</tex> {{---}} размер массива
'''function''' push(element : '''T'''):
