Стек
Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент. Лучше всего понятие стека можно проиллюстрировать примером стопки книг: в стопку можно добавить еще одну книжку, положив ее сверху; из стопки можно взять, не разрушив ее, только верхнюю книгу. А для того, чтобы достать книжку из середины стопки, необходимо сначала убрать по одной все лежащие выше нее.
Последовательность обработки элементов стека хорошо отражают аббревиатуры LIFO (Last In First Out - "последним вошел, первым вышел") и FILO (First In Last Out - "первым вошел, последним вышел").
Реализовать стек можно любым удобным для программиста способом: например, массивом. Тогда началом стека (его "верхним" элементом) будет последний компонент массива, а освобождение стека будет происходить в направлении от конца массива к его началу. При такой реализации нет необходимости в постоянном перемещении компонент массива.
Впрочем, наиболее эффективной все равно будет реализация при помощи односвязного линейного списка, о котором пойдет речь в следующей лекции.
