Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

infa_1 / 9.Стек

..doc
Скачиваний:
35
Добавлен:
05.06.2015
Размер:
31.74 Кб
Скачать

9.Стек.

Помимо списка используются две его разновидности – стек и очередь.

Стек – линейный список, в котором добавление и исключение возможны только в конце.

Очередь – линейный список, элементы которого добавляются только в конец, а исключаются из начала.

Стек — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

Программный вид стека используется для обхода структур данных, например, дерево или граф. При использовании рекурсивных функций также будет применяться стек, но аппаратный его вид. Кроме этих назначений стек используется для организации стековой машины. Для отслеживания точек возврата из подпрограмм используется стек вызовов. Идея стека используется в стековой машине среди стековых языков программирования.

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)[5].

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

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