Операционные системы -вопросы теории

Стек Стек или магазин — это структура



Стек

Стек, или магазин — это структура данных, над которой мы можем осуществлять две операции: проталкивание (push) значения и выталкивание (pop). Значения выталкиваются из стека в порядке, обратном тому, в котором проталкивались: LIFO (Last In, First Out, первый вошел, последний вышел). Стековые структуры находят широкое применение при синтаксическом разборе арифметических выражений и алголоподобных языков программирования [Кормен/Лейзерсон/Ривест 2000].

Самая простая реализация стека — это массив и индекс последнего находящегося в стеке элемента (Рисунок 2.7). Этот индекс называется указателем стека (SP - Stack Pointer). Стек может расти как вверх, так и вниз [(Рисунок 2.8). Широко применяются также реализации стеков в виде односвяз-|ных списков.



Содержание раздела