Очереди и стеки

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

По своему существу очередь является сугубо динамическим объектом: с течением времени и длина очереди, и набор образующих ее элементов изменяются. Заметим, что структура данных, называемая очередью, используется и как средство программирования при решении различных задач, в том числе и не связанных с реальными очередями.

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

Различают два основных вида очередей, отличающиеся по дисциплине обслуживания находящихся в них элементов. При первой из дисциплин (которая обычно используется в очередях реальной жизни) заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Эту дисциплину обслуживания очереди принято называть FIFO (First In — First Out, т.е. первый в очередь — первый из очереди). Поскольку очереди с такой дисциплиной обслуживания используются в программировании относительно редко, то предлагаем читателю в качестве упражнений определить средствами паскаля такую очередь и дать описание процедур, реализующих упомянутые операции над очередью.

Более подробно остановимся на очереди с такой дисциплиной обслуживания, при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Эту дисциплину обслуживания принято называть LIFO (Last In — First Out, т.е. последний в очередь — первый из очереди). Очередь такого вида в программировании принято называть стеком (магазином). Это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.

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

Теперь отобразим стек на подходящую структуру данных языка паскаль. Среди всех возможных способов такого отображения отдадим предпочтение способу, который обеспечивает наиболее быстрое выполнение основных операций над стеком, а именно: представим стек в виде динамической цепочки звеньев. Будем исходить из того, что вершиной стека является первое звено цепочки (можно было бы считать, что вершиной является последнее звено). А поскольку в стеке доступна только его вершина, то в отличие от представления рассмотренных ранее динамических структур заглавное звено в цепочке становится излишним. В этом случае значением указателя, представляющего стек как единый объект, является ссылка на вершину стека. Как обычно в случае цепочки, каждое ее звено содержит ссылку на следующее звено цепочки, причем «дно» стека (элемент, занесенный в стек раньше всех) имеет ссылку nil.

Таким образом, тип значения (структуры данных), которое будет представлять стек, можно задать с помощью следующих описаний типов:

type

типэлем={имя или задание типа элементов стека} связь = Тзвеностека; звеностека = record

след: связь; элем: типэлем

end;

стек = связь;

Реальный стек можно ввести в употребление с помощью соответствующего описания переменной, например:

var

р: стек;

Схематично стек можно изобразить следующим образом (указатель р ссылается на вершину стека):

Если стек р пуст, то значением указателя р является ссылка nil. К началу использования стека его необходимо сделать пустым, что обеспечивается оператором присваивания:

р:=nil

Рассмотрим реализацию основных операций над стеком.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >