Учебно-методическое пособие. Алматы, 2017 ббк

1.4.3 Стек

Представьте себе, что вы пошли на рынок за покупками. Делая покупки, вы складываете их в сумку. Вернувшись домой, вы начинаете выкладывать покупки из сумки. Что вы вынете раньше? Конечно, то, что было положено в сумку последним. Для того, что бы составить пирамидку, мы поочередно надеваем на ось колечки (см. рис.1.15.). После того как мы сложили пирамидку, что бы достать первое колечко придется снять все колечки, которые находящиеся над ним. При этом порядок снятия колечек будет обратным, то есть сначала снимается последней колечко, затем - предпоследнее и так до тех пор, пока не снимем первое. В этих двух примерах, по аналогии с очередью, можно сказать, что мы имеем дело с принципом «Первый пришел, последним ушел!» или на английском языке: «First input, Last output» (FILO) или «Последним пришел, первым ушел!» или на английском языке: «Last input, First output» (LIFO). Организацию хранения и обработки линейных списков в котором применяется данный принцип называют стеком.

При удалении элемента из вершины стека мощность (глубина) стека уменьшается на единицу, но сдвижки элементов не происходит.