1. Стеки
 

Структура, отражающая отношение соседства между своими элементами, называется линейной. К линейным структурам можно отнести массивы, очереди, стеки, деки, линейные списки.

Структуры стека. Стек — это динамически изменяемый упорядоченный набор элементов. Помещение элементов в стек и выборка их из него производятся с одного и того же конца, который называется вершиной стека, т.е. выборка элементов из стека осуществляется в порядке, обратном их засылке. Это правило формулируется так: «последним пришел, первым ушел» (LIFO: «Last Input — First Output»).

Области применения стека:

• передача параметров в функции;
• трансляция (синтаксический и семантический анализы, генерация кодов и т.д.);
• реализация рекурсии в программировании;
• реализация управления динамической памятью и т.п.

Стеки могут представляться в памяти либо в виде вектора, либо в виде цепного списка.

При векторном представлении под стек отводится сплошная область памяти, достаточно большая, чтобы в ней можно было поместить некоторое максимальное число элементов, которое определяется решаемой задачей. Граничные адреса этой области являются параметрами физической структуры стека - вектора. В процессе заполнения стека место последнего элемента (его адрес ) помешается в указатель вершины стека. Если указатель выйдет за верхнюю границу стека, то стек считается переполненным и включение нового элемента становится невозможным. Поэтому для стека надо отводить достаточно большую память, однако если стек в процессе решения задачи заполняется только частично, то память используется неэффективно. Так как под стек отводится фиксированный объем памяти, а количество элементов переменно, то говорят, что стек в векторной памяти - это полустатическая структура данных. Обычно в стеке элементы имеют один и гот же тип, поэтому обработка такого стека достаточно проста.

Многие современные ЭВМ содержат в своей конструкций аппаратные стеки или средства работы со стеками. Однако даже в этом случае при разработке программ часто приходится использовать свои программные стеки. Стек, представленный как век гор, имеет вид:

  Структура стека в векторной памяти

    Списковая структура стека

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