В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 63
Текст из файла (страница 63)
Элементами очереди в общем случае являются заказы на то или иное обслуживание: выбить чек на нужную сумму в кассе магазина, получить нужнуюинформацию в справочном бюро, выполнить очередную операцию по обработке детали на данном станке в автоматической линии и т.д. и т.п.В программировании имеется структура данных, которая называетсяочередь. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик (средняядлина очереди, время пребывания заказа в очереди, вероятность отказав постановке в очередь при ограничении ее максимальной длины и т.п.)при данном законе поступления заказов и дисциплине их обслуживания.276Ясно, что структура данных, используемая для этой цели, должна отражатьспецифику моделируемых объектов, т.е.
реальных очередей.Заметим, что по своему существу очередь является сугубо динамическим объектом — с течением времени и длина очереди, и набор образующихее элементов изменяются. Заметим также, что структура данных, называемая очередью, используется и как средство программирования при решении различных задач, в том числе и не связанных с реальными очередями.Над очередью определены две операции: занесение элемента (заказана обслуживание) в очередь и выбор элемента из очереди (для его обслуживания). При этом выбранный элемент, естественно, исключается из очереди.
В очереди доступны две позиции: ее начало (из этой позиции выбирается элемент из очереди) и конец (в эту позицию помещается заносимыйв очередь элемент).Различают два основных вида очередей, отличающиеся по дисциплинеобслуживания находящихся в них элементов. При первой из дисциплин(которая обычно используется в знакомых нам по реальной жизни очередях) заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Эту дисциплину обслуживания очередипринято называть FIFO (First In — First Out, т.е. первый в очередь — первый из очереди). Поскольку очереди с такой дисциплиной обслуживанияиспользуются в программировании относительно редко, то мы предлагаемчитателю в качестве упражнений определить средствами паскаля такуюочередь и дать описание процедур, реализующих упомянутые выше операции над очередью.Мы более подробно остановимся на очереди с такой дисциплиной обслуживания, при которой на обслуживание первым выбирается тот элементочереди, который поступил в нее последним.
Эту дисциплину обслуживания принято называть LIFO (Last In — First Out, т.е. последний в очередь первый из очереди). Очередь такого вида в программировании принятоназывать стеком (магазином) — это одна из наиболее употребительныхструктур данных, которая оказывается весьма удобной при решении различных задач.В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, называемая вершиной стека — это позиция, в которойнаходится последний по времени поступления в стек элемент.
Функционально стек похож на известную детскую игрушку "пирамидка". Когда мызаносим новый элемент в стек (надеваем на стержень пирамидки новоекольцо), то он помещается поверх прежней вершины (на предыдущеенадетое кольцо) и теперь уже сам находится в вершине стека. Выбратьэлемент можно только из вершины стека (с пирамидки можно снять только самое верхнее кольцо, которое было надето на стержень позднее всехостальных); при этом выбранный элемент исключается из стека, а в еговершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (то кольцо пирамидки, на котором лежалоснятое кольцо).Теперь отобразим стек на подходящую структуру данных языка Паскаль.
Среди всех возможных способов такого отображения мы отдадимпредпочтение способу, который обеспечивает наиболее быстрое выполнение основных операций над стеком, а именно — представим стек в виде277динамической цепочки звеньев. Мы будем исходить из того, что вершинойстека является первое звено цепочки (можно было бы считать, что вершиной является последнее звено). А поскольку в стеке доступна только еговершина, то — в отличие от представления рассмотренных ранее динамическ и х структур — заглавное звено в цепочке становится излишним. В этомслучае значением указателя, представляющего стек как единый объект,является ссылка на вершину стека.
Как обычно в случае цепочки, каждоеее звено содержит ссылку на следующее звено цепочки, причем "дно"стека (элемент, занесенный в стек раньше всех) имеет ссылку nil.Таким образом, тип значения (структуры данных), которое будет представлять стек, можно задать с помощью следующих описаний типов:typeтипэлем={имя или задание типа элементов стека>связь = *звеностека;звеностека » recordслед; связь;элем: типэлемend;стек = связь:Реальный стек можно ввести в употребление с помощью соответствующегоописания переменной, например:varр: стек;Схематично стек можно изобразить следующим образом (указатель р ссылается на вершину стека):Если стек р пуст, то значением указателя р является ссылка nil. К началуиспользования стека его необходимо сделать пустым, что обеспечиваетсяоператором присваиванияр:=ni1Рассмотрим реализацию основных операций над стеком.Занесение элемента в стек.
Поскольку при решении задачи может использоваться несколько различных стеков, то процедура занесения в стекдолжна иметь два параметра: один из них задает нужный стек, а другой —заносимое в него значение.Описание этой процедуры может иметь вид:procedure ВСТЕК (var st: стек; новэл: типэлем);var q: связь;begin{создание нового звена)new(q);278qt.элем:=новэл;{созданное звено сделать вершиной стека}Я + .след:=з<:; st: =qendВыбор элемента из стека. При выполнении этой операции элемент, находящийся в вершине стека, должен быть присвоен в качестве значениянекоторой переменной, а звено, в котором был представлен этот элемент,должно быть исключено из стека. Процедуру, реализующую эту операцию,можно описать следующим образом:procedure ИЗСТЕКА (var st:стек; var а: типэлем);begin {а:= значение из вершины стека}а:=st t.элем;{исключение первого звена из стека}st:=st + .следendПравда, стремясь к максимальному быстродействию этой процедуры, мынаделили ее двумя недостатками.
Во-первых, исключаемое по этой процедуре звено стека не уничтожается, что приводит к менее эффективномуиспользованию памяти машины. Во-вторых, здесь предполагается, чтов программе стек используется корректно, т.е. что при обращении к этойпроцедуре указанный стек заведомо не пуст. В противном случае результатвыполнения оператора процедуры оказывается неопределенным, а этоможет привести к неверным результатам.
Таким образом, ответственностьза корректное использование стеков мы возложили на программиста,который будет использовать это описание процедуры в своей программе.Для избежания возможности получения неверных результатов (особеннопри решении ответственных задач) можно в самом описании процедурыпредусмотреть контроль корректности использования заданного стека.Если этот стек оказался пустым, то можно, например, вывести на печатьсоответствующее сообщение и с помощью оператора перехода осуществитьпереход на конец программы.
В этом случае требуется, чтобы перед заключительным символом end программы находился пустой оператор, помеченный заранее фиксированной меткой. Мы, ради простоты, сведем выполнение соответствующего оператора процедуры к печати диагностическогосообщения:procedure ИЗСТЕКАСКОНТР (var st: стек; var а: типэлем);var q: связь;begin {проверка, не пуст ли стек}if st=nil thenbegin writeln;writeln('ПОПЫТКА_ВЫБОРА_ИЗ_ПУСТОГО_СТЕКА')endel sebegin {выбор элемента из вершины}a:=st t.элем;279{запоминание ссылки на старую вершину}q:=st;{исключение и уничтожение использованного эвена}st:=st•.след;dispose(q)endendЗдесь следует обратить внимание на достаточно типичную возможнуюошибку: если не ввести в употребление вспомогательную ссылочную переменную q, а для уничтожения звена использовать оператор процедурыdispose(st), то это приведет к большим неприятностям (читателю предлагается проанализировать этот случай и выяснить, что произойдет в результате выполнения такой процедуры).А теперь рассмотрим конкретную задачу, при решении которой удобновоспользоваться стеком.П ри м е р 14.2.
Во внешнем текстовом файле input задана строка литер,признаком конца которой является первая по порядку точка. В строкемогут содержаться круглые, квадратные и фигурные скобки - как открывающие, так и закрывающие.Требуется проверить баланс скобок в заданной строке.Баланс скобок соблюдается, если выполнено каждое из следующихусловий:1) для каждой открывающей скобки справа от нее есть соответствующаязакрывающая скобка, и наоборот, для каждой закрывающей скобки слеваот нее есть соответствующая открывающая скобка:2) соответствующие пары скобок (открывающие и закрывающие) разных типов правильно вложены друг в друга.
Например, в строке[ (х + у)*(х + 2)1 { 3 + abs(x)} + d] *е баланс скобок соблюдается, а в строке [{ g + h[i] ((х - a ) ] d ) ) - нет.В качестве результата на печать вывести соответствующее сообщение особлюдении баланса, а также начало строки до первого по порядку нарушения баланса скобок (или всю строку, если баланс соблюдается).Можно предложить следующую идею алгоритма решения поставленнойзадачи с использованием стека. Первоначально сформируем пустой стек.Затем будем последовательно просматривать литеры строки.
Если очередная литера окажется одной из открывающих скобок, занесем ее в стек.Если очередная литера окажется закрывающей скобкой, выберем последнюю из занесенных в стек открывающих скобок и сравним эти скобкина соответствие друг другу. Если соответствие имеет место, то эффект должен быть такой же, как если бы этой пары скобок в строке вообще небыло. Если эти две скобки не соответствуют друг другу (например, очередная обнаруженная в строке закрывающая скобка — круглая, а из вершиныстека выбрана квадратная открывающая скобка), то не выполнено второеусловие соблюдения баланса скобок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
