Лабораторная работа №2

Стеки, очереди деки.

1. Цель работы

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

2. Краткие сведения из теории

2.1. Стеки, очереди, деки

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

2.1.1. Стеки

Стек – структура данных с односторонним доступом, хранящая последовательность значений, для которой определены следующие операции:

• очистить стек (сделать структуру пустой);
• проверить на пустоту;
• добавить элемент;
• взять элемент;
• прочитать элемент;
• записать элемент.

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

При «добавлении элемента» новое значение добавляется в конец стека. При выполнении операции «взять элемент» – извлекается из него. Операции «прочитать элемент» и «записать элемент» работают с вершиной стека.

Говорят, что стек работает по принципу 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);

Сформирует список следующего вида:

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

2.1.2. Очереди

Очередь – структура данных с двусторонним доступом, хранящая последовательность значений, для которой определены следующие операции:

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

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

Про очередь говорят, что она работает по принципу 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 будет представлена так:

2.1.3. Деки

Дек – структура данных с двусторонним доступом, хранящая упорядоченное множество значений, для которой определены следующие операции:

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

Как видно, дек содержит операции, описанные выше для стека и очереди. Для представления дека используются те же наборы переменных, что и для очереди.

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

2.2. Вычисление арифметических выражений

Рассмотрим яркий пример применения стеков – вычисление арифметических выражений. При решении этой задачи на компьютере возникают две проблемы:

1. Как учитывать приоритет операций (сначала вычисляются операции умножения и деления, как имеющие более высокий приоритет по сравнению с операциями сложения и вычитания).
2. Как учитывать то, что скобки меняют обычный порядок вычисления выражения.

В остальных случаях выражение вычисляется слева направо. Само вычисление слева направо трудностей не вызывает.

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

2.2.1. Обратная польская запись

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

Полезными свойствами польской записи являются:

1. любое арифметическое выражение можно записать в польской записи;
2. выражение, записанное в польской записи, всегда вычисляется строго слева направо.

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

2.2.2. Вычисление выражения в польской записи

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

Запишем рекурсивное определение польской записи для операций '+', '–', '*', '/'. Обратной польской записью является любое выражение, определяемое правилами (A – операнд, V – выражение в польской записи):

1. А;
2. VV+;
3. VV–;
4. VV*;
5. VV/.

Например, следующие выражения корректны в польской записи:

а) 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;

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

2.2.3. Преобразование из арифметической в польскую запись

Сначала рассмотрим преобразование для выражений, не содержащих скобки.

Выражение в польской записи будем формировать, а исходное выражение – просматривать слева направо. Будем предполагать, что исходное выражение корректно.

В исходном выражении могут встретиться только следующие лексемы:

• операнд;
• знак операции.

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

Пусть

Приоритет(‘+’)=Приоритет(‘–’)=1, а

Приоритет(‘*’)=Приоритет(‘/’)=2.

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

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

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

Рассмотрим работу алгоритма на примере выражения 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 – число лексем в исходном выражении. За один проход мы преобразуем выражение из арифметической записи в польскую, а еще за один вычислим значение выражения в польской записи. Остается только добавить, что оба эти прохода можно объединить в один.

2.3. Дисциплины распределения ресурсов

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

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

1. Дисциплина обслуживания в порядке поступления.
2. Дисциплина обслуживания в порядке обратном порядку поступления.
3. Круговой циклический алгоритм.
4. Обслуживание с абсолютным приоритетом.
5. Обслуживание с относительным приоритетом.

Во всех дисциплинах главным вопросом является вопрос, где хранить запросы, ожидающие обработки. Также важным показателем является среднее время ожидания обработки запроса.

2.3.1. Обслуживание в порядке поступления

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

Преимуществом такой дисциплины является простота реализации. Среднее время ожидания обработки запроса при установившихся темпах обслуживания и поступления новых запросов одинаково для всех процессов.

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

2.3.2. Обслуживание в обратном порядке

Это еще одна простая в своей реализации дисциплина распределения ресурсов. Она предполагает, что запросы от процессов попадают в стек и извлекаются из него по мере обработки.

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

2.3.3. Круговой циклический алгоритм

Вернемся к обслуживанию в порядке поступления. В том случае, если какой-то процесс будет слишком долго держать критический ресурс, остальные процессы будут просто простаивать в ожидании. Чтобы этого избежать, фиксируем некоторое время t и ограничим им время обработки запроса. Если за это время запрос не был полностью обработан, то опять заносим его в конец очереди с информацией о стадии обработки запроса. Когда опять настанет его черед, обработка продолжится с того места, на котором была остановлена.

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

Заметим, что время обработки запросов с большим временем обработки при использовании кругового циклического алгоритма существенно возрастает. Таким образом, можно говорить о благоприятствовании коротким запросам и дискриминации длинных запросов.

2.3.4. Обслуживание с абсолютным приоритетом

2.3.5. Обслуживание с относительным приоритетом

3. Контрольные вопросы

1. Что такое инфиксная запись операций? Что такое постфиксная запись?
2. Приведите рекурсивное определение польской записи. Докажите, что примеры а) – б) из раздела 2.2.2. удовлетворяют этому определению.
3. Докажите, что после окончания работы алгоритма из раздела 2.2.2. в стеке останется только одно значение и что оно будет значением выражения.
4. Покажите процесс преобразования арифметической записи 1+2/(3*(4+5)-6) в польскую, составив таблицу, подобную приведенной в разделе 2.2.3.
5. Что такое критический ресурс? Что такое дисциплина распределения ресурсов?
6. Перечислите базовые дисциплины распределения ресурсов.

6. Задания для индивидуальной работы

Задание 1. Написать программу – калькулятор, вычисляющую значение арифметического выражения. Выражение может содержать операнды, скобки и знаки операций. Операнды – целые числа. В выражении могут быть использованы бинарные операции: сложение, вычитание, умножение, деление и возведение в степень, – и унарные: унарный минус и квадратный корень.

Указания. Унарный минус встречается только в начале выражения или после открывающей скобки. Унарный минус при преобразовании в польскую запись лучше заменить другим символическим обозначением (например, ‘$’). Также не стоит забывать, что возведение в степень и извлечение корня обладают большим приоритетом, чем приоритет арифметических операций.