21. Методы реализации стеков

Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной.

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

При векторном представлении под стек отводится сплошная область памяти, достаточно большая, чтобы в ней можно было поместить некоторое максимальное число элементов, которое определяется решаемой задачей.

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

Если указатель выйдет за верхнюю границу стека, то стек считается переполненным и включение нового элемента становится невозможным. Стек в векторной памяти - это полустатическая структура данных.

При списковом представлении стека память под дескриптор и под каждый элемент стека получают динамически.

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

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

22. Применение стеков при разработке приложений

Одно из применений стеков можно продемонстрировать на примере вычисления значения арифметического выражения в калькуляторах.

Алгоритм вычисления предусматривает представление выражения в определенном формате. Различают представление выражения в инфиксной и постфиксной формах. В обеих формах выражения представляются в виде символьных строк.

В инфиксной форме записи каждый бинарный оператор помещается между двумя своими операндами

15*4+(25/2-3)^2=

Постфиксный калькулятор.

Из исходной строки выделяется очередной элемент.

Если элемент - число, то оно заносится в стек. Переход к п.1.

Если элемент - оператор, то из стека последовательно извлекаются два элемента, сначала правый операнд, затем левый операнд и над ними выполняется операция, определенная оператором. В стек.

23. Абстрактный тип данных «Очередь»

По своему существу очередь является полустатической структурой - с течением времени и длина очереди, и состав могут изменяться.

Элементы могут удаляться только из начала очереди. Очереди находят широкое применение в операционных системах (очереди задач, буфера ввода-вывода, буфер ввода с клавиатуры, очереди в сетях ЭВМ и т.п.), при моделировании реальных процессов и т.д.

Очереди могут иметь векторную или списковую структуру хранения, в свою очередь векторная структура может занимать статическую либо динамическую память.

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

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