Эти структуры данных не случайно рассматриваются вместе. Все они хранят некоторую последовательность значений, и доступ к этой последовательности ограничен (нельзя прочитать произвольный элемент последовательности). Для этих структур определяется набор допустимых операций, с помощью которых можно записывать и читать элементы последовательностей. То есть эти структуры данных определяются на уровне функциональной спецификации (набора процедур).
Стек – структура данных с односторонним доступом, хранящая последовательность значений, для которой определены следующие операции:
Особенностью стека является то, что в каждый момент времени мы имеем доступ лишь к одному элементу, который находится в конце стека – вершине стека.
При «добавлении элемента» новое значение добавляется в конец стека. При выполнении операции «взять элемент» – извлекается из него. Операции «прочитать элемент» и «записать элемент» работают с вершиной стека.
Говорят, что стек работает по принципу LIFO (Last in – first out; последним пришел – первым ушел).
Существуют два принципиально различных способа хранения стеков в памяти ЭВМ: хранение в виде массива последовательно расположенных элементов и хранение в виде односвязного списка.
Пусть элементами стека будут значения типа TItem.
Рассмотрим хранение стека в массиве. Для этого способа достаточно завести две переменные:
Var
Top: Integer; {индекс вершины стека, число элементов в стеке}
Stack: array[1..MaxSize] of TItem; {массив элементов стека}
Рассмотрим реализацию операций из функциональной спецификации стека.
Очистить стек. Для очистки стека достаточно обнулить индекс вершины стека Top. Нет никакой необходимости в физическом уничтожении данных:
procedure ClearStack;
begin
Top := 0;
end;
Проверка на пустоту:
function IsEmpty: Boolean;
begin
IsEmpty := Top=0;
end;
Чтение элемента:
function Get: TItem;
begin
if Top=0 then RunError else Get := Stack[Top];
end;
Запись элемента:
procedure Put(Item: TItem);
begin
if Top=0 then RunError else Stack[Top] := Item;
end;
Добавление элемента:
procedure Push(Item: TItem);
begin
if Top=MaxSize then RunError;
Inc(Top); Stack[Top] := Item;
end;
Взятие элемента:
function Pop: TItem;
begin
if Top=0 then RunError;
Item := Stack[Top]; Dec(Top);
end;
Второй способ хранения стека предполагает размещение стека в динамической памяти. Фактически стек хранится в однонаправленном списке. Указатель на начало списка является в то же время указателем на вершину стека (УВС).
Type
PElement = ^TElement;
TElement = record
Item: TItem;
Next: PElement;
end;
Var
TopPointer: PElement;
Рассмотрим реализацию основных операций над стеком для такого способа хранения.
Очистить стек. В данном случае надо обязательно физически освободить всю память, выделенную под элементы стека:
procedure ClearStack;
Var
Temp: PElement;
begin
while TopPointer<>nil do
begin
Temp := TopPointer;
TopPointer := TopPointer^.Next;
Dispose(Temp);
end;
end;
Проверка на пустоту:
function IsEmpty: Boolean;
begin
IsEmpty := TopPointer=nil;
end;
Чтение элемента:
function Get: TItem;
begin
if TopPointer=nil then RunError else Get := TopPointer^.Item;
end;
Запись элемента:
procedure Put(Item: TItem);
begin
if TopPointer=nil then RunError else TopPointer^.Item := Item;
end;
Добавление элемента. При добавлении надо выделить память под новый элемент стека:
procedure Push(Item: TItem);
Var
Temp: PElement;
begin
Temp := New(PElement);
Temp^.Item := Item;
Temp^.Next := TopPointer;
TopPointer := Temp;
end;
Взятие элемента должно сопровождаться освобождением памяти, которую он занимал в куче:
function Pop: TItem;
Var
Temp: PElement;
begin
if TopPointer=nil then RunError;
Item := TopPointer^.Item;
Temp := TopPointer^.Next;
Dispose(TopPointer);
TopPointer := Temp;
end;
Например, последовательность операторов
ClearStack;
Push(3); Push(7); Push(2); Push(1);
Сформирует список следующего вида:
Преимуществом спискового хранения является то, что нет необходимости резервировать память для максимально возможного числа элементов стека, что требуется при хранении в массиве. На практике же удобным оказывается хранение в массиве, так как при операции «очистить стек» не нужно пробегать весь стек – очистка производится в одно действие.
Очередь – структура данных с двусторонним доступом, хранящая последовательность значений, для которой определены следующие операции:
Операции похожи на те, что были описаны в стеке. Отличие лишь в том, что добавление элемента происходит в конец очереди, а удаление – из ее начала. Структура данных очередь полностью аналогична обыденному пониманию этого слова. Когда человек занимает очередь в магазине, он становится в конец очереди, так и элемент добавляемый в очередь дописывается в ее конец. Когда приходит очередь брать товар, человек берет товар и уходит, так и при извлечении элемент берется из начала очереди.
Про очередь говорят, что она работает по принципу FIFO (First in – first out; первым пришел – первым ушел).
При хранении в массиве уже не хватит двух переменных, как этого было достаточно для стека. Можно обойтись тремя переменными. Безусловно, нужен массив для хранения содержимого очереди. Этот массив будет «свернут в кольцо», то есть элементом следующим за последним элементом массива будет считаться первый элемент массива. Помимо массива можно завести переменные для хранения начала и конца очереди. Но тут встает вопрос, как определить пустоту очереди и ее переполненность (когда все элементы массива заняты очередью, добавление становится невозможным – возникает переполнение). Очередь будет считаться пустой, когда индекс начала на единицу больше индекса конца, но то же самое будет и при очереди, заполнившей весь массив!!! Поэтому лучше ввести следующие три переменные:
Var
Beginning, {индекс начала очереди}
Size: Integer; {размер очереди}
Queue: array[0..MaxSize-1]of TItem; {массив элементов очереди}
Этих трех переменных достаточно для реализации основных операций над очередью. Индекс конца очереди можно найти следующим образом (здесь воспользуемся тем, что массив «свернут в кольцо»):
Extremity := (Beginning+Size)mod MaxSize;
Рассмотрим реализацию основных операций над очередью.
Очистка очереди:
procedure ClearQueue;
begin
Beginning := 0; Size := 0;
end;
Проверка пустоты:
function IsEmpty: Boolean;
begin
IsEmpty := Size=0;
end;
Добавление элемента в конец очереди:
procedure Push(Item: TItem);
begin
if Size=MaxSize then RunError;
Inc(Size); Queue[(Beginning+Size)mod MaxSize] := Item;
end;
Взятие элемента из начала очереди:
function Pop: TItem;
begin
if Size=0 then RunError;
Pop := Queue[Beginning]; Dec(Size);
if Beginning=MaxSize-1 then Beginning := 0
else Inc(Beginning);
end;
Прочитать первый элемент:
function GetFirst: TItem;
begin
if Size=0 then RunError;
GetFirst := Queue[Beginning];
end;
Записать последний элемент:
procedure PutLast(Item: TItem);
begin
if Size=0 then RunError;
Queue[(Beginning+Size)mod MaxSize] := Item;
end;
Для списочного хранения очереди потребуется еще один указатель – на конец очереди. Очередь будет храниться в виде двусвязного списка. Очередь из элементов 7 и 10 будет представлена так:
Дек – структура данных с двусторонним доступом, хранящая упорядоченное множество значений, для которой определены следующие операции:
Как видно, дек содержит операции, описанные выше для стека и очереди. Для представления дека используются те же наборы переменных, что и для очереди.
Наглядно дек можно представить в виде полки с книгами, которые можно доставать и помещать с двух сторон, но нельзя брать и ставить в середине полки.
Рассмотрим яркий пример применения стеков – вычисление арифметических выражений. При решении этой задачи на компьютере возникают две проблемы:
В остальных случаях выражение вычисляется слева направо. Само вычисление слева направо трудностей не вызывает.
Один из способов решения этих двух проблем – представление выражения в обратной польской записи, введенной польским математиком Лукашевичем.
Обычная запись арифметических выражений, принятая в математике, предполагает инфиксную запись операций, то есть знак операции ставится между операндами, к которым применяется. В обратной польской записи используется постфиксная запись операций. Это означает, что знак операции записывается не между операндами, а после них.
Полезными свойствами польской записи являются:
Второе свойство означает, что при вычислении значения выражения, записанного в польской записи, не надо учитывать приоритеты операций и выражение не содержит скобок, меняющих нормальный порядок вычислений. Следовательно, если записать выражение в польской записи, то алгоритм вычисления сильно упростится.
Пусть все операции бинарны, то есть имеют по два операнда. Таковы операции сложения, вычитания, умножения, деления. Как было сказано, выражения в польской записи всегда вычисляются слева направо. При этом знак операции применяется к двум предшествующим операндам. Надо не забывать, что эти операнды сами могут быть выражениями.
Запишем рекурсивное определение польской записи для операций '+', '–', '*', '/'. Обратной польской записью является любое выражение, определяемое правилами (A – операнд, V – выражение в польской записи):
Например, следующие выражения корректны в польской записи:
>а) 2 4 + (равносильно 2+4);
б) 1 2 3 * – (равносильно 1-(2*3)=1-2*3);
в) 1 2 3 – * (равносильно 1*(2-3));
г) 1 2 3 + 4 – / (равносильно 1/(2+3-4)).
Рассмотрим процесс вычисления. Выражение вычисляется слева направо. Как только встречается знак операции, он сразу же применяется к двум предшествующим операндам. Значения самих операндов при движении слева направо по выражению надо где-то сохранять. Поскольку нам всегда будут требоваться только значения последних просмотренных операндов, то следует воспользоваться такой структурой данных, как стек.
Таким образом, мы получаем следующий алгоритм вычисления арифметического выражения в польской записи в предположении, что исходное выражение корректно. Лексическими единицами (лексемами) будем считать операнд и знак операции.
<очистить стек>;
for i := 1 to <число лексических единиц> do
begin
Lex := <i-ая лексическая единица>;
if <Lex – знак операции> then
begin
Op2 := <взять из стека>;
Op1 := <взять из стека>;
case <Lex как знак операции> of
‘+’: Op := Op1+Op2;
‘-’: Op := Op1-Op2;
‘*’: Op := Op1*Op2;
‘/’: Op := Op1/Op2;
end;
<добавить в стек Op>;
end else
begin
<добавить в стек операнд Lex>
end;
end;
По окончании работы этого алгоритма в стеке останется лишь одно значение – значение арифметического выражения.
Сначала рассмотрим преобразование для выражений, не содержащих скобки.
Выражение в польской записи будем формировать, а исходное выражение – просматривать слева направо. Будем предполагать, что исходное выражение корректно.
В исходном выражении могут встретиться только следующие лексемы:
Приоритет операций умножения и деления выше приоритета операций сложения и вычитания. Операции, имеющие более высокий приоритет, должны быть вычислены в первую очередь (следовательно, встретиться в польской записи раньше, так как выражения в польской записи вычисляются строго слева направо).
Пусть
>Приоритет(‘+’)=Приоритет(‘–’)=1, а
Приоритет(‘*’)=Приоритет(‘/’)=2.
Для хранения встреченных в исходном выражении, но еще не занесенных в польскую запись знаков операций понадобится стек операций. Знак операции можно переносить из стека в результирующее выражение, если очередной знак операции имеет меньший или равный приоритет. Это будет гарантией соблюдения правильного порядка вычислений. Значит, встретив знак операции, программа должна перенести из вершины стека все операции, имеющие больший или равный приоритет, а затем добавить в стек встреченный знак.
По окончании просмотра исходного выражения все знаки операций, оставшиеся в стеке должны быть перенесены в результирующее выражение.
Встречая операнд, программа должна сразу записать его в польскую запись. При этом порядок следования операндов не изменится.
Рассмотрим работу алгоритма на примере выражения 1-2/3*4+5.
№ шага |
Текущая лексема |
Результирующее выражение |
Стек операций |
1 |
1 |
1 |
<> |
2 |
– |
1 |
<-> |
3 |
2 |
1 2 |
<-> |
4 |
/ |
1 2 |
<-,/> |
5 |
3 |
1 2 3 |
<-,/> |
6 |
* |
1 2 3 / |
<-, *> |
7 |
4 |
1 2 3 / 4 |
<-, *> |
8 |
+ |
1 2 3 / 4 * - |
<+> |
9 |
5 |
1 2 3 / 4 * - 5 |
<+> |
10 |
1 2 3 / 4 * - 5 + |
<> |
Пусть Source – исходное (арифметическое), а Destination – результирующее (в польской записи) выражение.
Программа, преобразующая Source в Destination, будет выглядеть так:
<очистить стек>;
<очистить Destination>;
for i := 1 to <число лексических единиц в Source> do
begin
Lex := <i-ая лексема Source>;
if <Lex – знак операции> then
begin
while (<стек не пуст>)and(Приоритет(Lex)>=
Приоритет(знак в вершине стека)) do
begin
Sign := <взять из стека>;
<Добавить Sign в Destination>;
end;
<добавить в стек знак операции Lex>;
end else
begin {Lex - операнд}
<Добавить операнд Lex в Destination>;
end;
end;
while <стек не пуст> do
begin
Sign := <взять из стека>;
<Добавить Sign в Destination>;
end;
Посмотрим, что изменится, если арифметические выражения будут содержать скобки.
В исходном выражении могут встретиться еще две лексемы, не перечисленные раньше:
С выражением внутри скобок алгоритм должен работать так же, как раньше. Встретив закрывающую скобку, программа будет переносить из стека операций в результирующее выражение все операции, занесенные после соответствующей открывающей скобки. Чтобы проще было отделять такие операции, удобно, встретив открывающую скобку, занести ее в стек операций.
Чтобы открывающая скобка не была вытеснена раньше времени из стека операций, она должна иметь самый высокий приоритет, поэтому условимся, что
Приоритет(‘(’)=3.
Тогда, встретив открывающую скобку, программа должна добавить ее в стек операций, а, встретив закрывающую скобку, – перенести из стека в результирующее выражение все знаки операций, пока не встретится открывающая скобка, и извлечь из стека саму открывающую скобку.
В остальном преобразование выражения не изменится. Правда стоит заметить, что если исходное выражение заключить в скобки, то стек операций после просмотра выражения будет пуст и от последнего цикла программы можно будет отказаться.
Программа примет следующий вид:
<очистить стек>;
<очистить Destination>;
Source := ‘(’+Source+‘)’;
for i := 1 to <число лексических единиц в Source> do
begin
Lex := <i-ая лексема Source>;
if <Lex – знак операции> then
begin
while (<стек не пуст>)and(Приоритет(Lex)>=
Приоритет(знак в вершине стека)) do
begin
Sign := <взять из стека>;
<Добавить Sign в Destination>;
end;
<добавить в стек знак операции Lex>;
end else
if <Lex – открывающая скобка> then
begin
<добавить в стек Lex>;
end else
if <Lex – закрывающая скобка> then
begin
while <в вершине стека не открывающая скобка> do
begin
Sign := <взять из стека>;
<Добавить Sign в Destination>;
end;
Sign := <взять из стека>; {удаление скобки
из стека}
end else
begin {Lex - операнд}
<Добавить операнд Lex в Destination>;
end;
end;
Преимущества использования польской записи для вычисления значения арифметического выражения очевидны: с их помощью это можно сделать за число действий порядка N, где N – число лексем в исходном выражении. За один проход мы преобразуем выражение из арифметической записи в польскую, а еще за один вычислим значение выражения в польской записи. Остается только добавить, что оба эти прохода можно объединить в один.
Рассмотрим такую ситуацию. Существует какой-то ресурс (таким ресурсом может быть, например, процессорное время). Несколько процессов конкурируют друг с другом за право пользования данным ресурсом. Такой ресурс называют критическим. В конкретный момент времени только один из процессов может владеть критическим ресурсом – остальные ждут его освобождения.
Поскольку невозможно выделить ресурс сразу всем, надо где-то запоминать поступающие запросы на его выделение, потом обслуживать их в некотором порядке. В такой ситуации должно быть какое-то правило, по которому ресурс будет выделяться одному из процессов. Остальные процессы будут ждать своей очереди. Эти правила называют дисциплинами распределения ресурсов. Рассмотрим следующие базовые дисциплины распределения ресурсов:
Во всех дисциплинах главным вопросом является вопрос, где хранить запросы, ожидающие обработки. Также важным показателем является среднее время ожидания обработки запроса.
В этом случае, поступающие запросы попадают в конец очереди запросов. Первыми обслуживаются запросы, находящиеся в начале очереди.
Преимуществом такой дисциплины является простота реализации. Среднее время ожидания обработки запроса при установившихся темпах обслуживания и поступления новых запросов одинаково для всех процессов.
Эта дисциплина обеспечивает уравнительную справедливость для всех процессов независимо от их важности и времени обработки запросов.
Это еще одна простая в своей реализации дисциплина распределения ресурсов. Она предполагает, что запросы от процессов попадают в стек и извлекаются из него по мере обработки.
Среднее время обработки запроса при установившихся темпах обслуживания и поступления новых запросов здесь также одинаково для всех процессов и не зависит от важности процесса. Однако всякий запрос должен сначала дождаться, пока будут обработаны запросы, поступившие после него.
Вернемся к обслуживанию в порядке поступления. В том случае, если какой-то процесс будет слишком долго держать критический ресурс, остальные процессы будут просто простаивать в ожидании. Чтобы этого избежать, фиксируем некоторое время t и ограничим им время обработки запроса. Если за это время запрос не был полностью обработан, то опять заносим его в конец очереди с информацией о стадии обработки запроса. Когда опять настанет его черед, обработка продолжится с того места, на котором была остановлена.
Тем самым мы добьемся того, что запросы с маленьким временем обработки не будут долго ждать, пока обработаются ранее поступившие запросы с большим временем обработки. В лучшем случае время обработки всех запросов будет меньше t. Тогда эта дисциплина выродится в обслуживание в порядке поступления.
Заметим, что время обработки запросов с большим временем обработки при использовании кругового циклического алгоритма существенно возрастает. Таким образом, можно говорить о благоприятствовании коротким запросам и дискриминации длинных запросов.
Задание 1. Написать программу – калькулятор, вычисляющую значение арифметического выражения. Выражение может содержать операнды, скобки и знаки операций. Операнды – целые числа. В выражении могут быть использованы бинарные операции: сложение, вычитание, умножение, деление и возведение в степень, – и унарные: унарный минус и квадратный корень.
Указания. Унарный минус встречается только в начале выражения или после открывающей скобки. Унарный минус при преобразовании в польскую запись лучше заменить другим символическим обозначением (например, ‘$’). Также не стоит забывать, что возведение в степень и извлечение корня обладают большим приоритетом, чем приоритет арифметических операций.