Теоретический материал: стеки, очереди, кольца (Паскаль)

Очередь. Основные операции над очередью

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

Изобразим очередь графически:

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

Очередь является динамической структурой – с течением времени изменяется и колчество, и набор составляющих ее элементов.

Опишем очередь на языке программирования:

Type
  EXO = ^O;
  O = record
       Data : integer;
       Next : EXO;
  end;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

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

Var
BeginO, EndO : EXO;

где BeginO – соответствует началу очереди и будет использоваться для удаления элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.

Занесение элемента в очередь

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

Procedure writeO(Var BeginO, EndO : EXO; c : integer);
Var
  u : EXO;
Begin
  new(u);
  u^.Data := c;
  u^.Next := Nil;
  if BeginO = Nil {проверяем, пуста ли очередь}
    then
      BeginO := u {ставим указатель начала очереди на первый созданный элемент}
    else
      EndO^.Next := u; {ставим созданный элемент в конец очереди}
  EndO := u; {переносим указатель конца очереди на последний элемент}
End;

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

Извлечение элемента из очереди

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

Procedure readO(Var BeginO : EXO; Var c : integer);
Var
  u : EXO;
Function FreeO(x1 : EXO): boolean;
Begin
  FreeO := (x1 = Nil);
End;
Begin
  if FreeO(BeginO)
    then
      writeln('Очередь пуста')
    else
      begin
        c := BeginO^.Data; {считываем искомое значение в переменную с}
        u := BeginO; {ставим промежуточный указатель на первый элемент очереди}
        BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
        dispose(u); {освобождаем память, занятую уже ненужным первым элементом}
      end;
End;

Задание. Напишите программу, содержащую все необходимые процедуры и функции работы с очередью.

Примеры решения задач

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

Пример 1. За один просмотр файла действительных чисел напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.

Program MordovskihK;
Type
  EXO = ^O;
  O = record
       Data : real;
       Next : EXO;
  End;
Var
  i, a, b : Real;
  Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO;
  f : File of real;
  Stroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : real);
  . . .
Procedure Print(u : EXO);
  . . .
Begin
  Min := Nil;
  Vibr := Nil;
  Other := Nil;
  EndMin := Nil;
  EndVibr := Nil;
  EndOther := Nil;
  writeln ('Введите имя файла >');
  readln(Stroka);
  writeln ('Введите промежуток >');
  readln(a, b);
  assign(f, Stroka);
  reset(f);
  while not Eof(f) do
    begin
      read(f, i);
        if i<a
          then
            writeO(Min, EndMin, i)
          else
            if (i>=a) and (i<=b)
              then
                writeO(Vibr, EndVibr, i)
              else
                writeO(Other, EndOther, i)
    end;
  close(f);
  writeln('Числа, меньшие ', а);
  Print(Min);
  writeln('Числа из промежутка [', а, ',' , b, ']');
  Print(Vibr);
  writeln('Числа, большие ', b);
  Print(Other);
End.

Пример 2. Из заданного текста перенести все цифры в конец каждой строки, сохранив их порядок.

Program BaranovA;
Type
  EXO = ^O;
  O = record
       Data : char;
       Next : EXO;
  End;
Var
  O1, EndO1, O2, EndO2 : EXO;
  f1, f2 : text;
  Name, NewName, Stroka, NewStroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : char);
  . . .
Procedure readO(var u : EXO, var c: char);
  . . .
Procedure ModifStr(St : string; var NewSt : string);
Var
  i : integer;
  l : char;
begin
  O1 := Nil;
  EndO1 := Nil;
  O2 := Nil;
  EndO2 := Nil;
  NewSt := '';
  for i := 1 to Length(St) do
    if St[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '8', '9', '0']
      then
        writeO(O2, EndO2, St[i])
      else
        writeO(O1, EndO1, St[i]);
  while O1 <> Nil do
    begin
      readO(O1, l);
      NewSt := NewSt + l;
    end;
  while O2 <> Nil do
    begin
      readO(O2, l);
      NewSt := NewSt + l;
    end;
End;
Begin
  write('Введите имя исходного файла: ');
  readln(Name);
  write('Введите имя файла-результата: ');
  readln(NewName);
  assign(f1, Name);
  assign(f2, NewName);
  reset(f1);
  rewrite(f2);
  while not Eof(f1) do
    begin
      readln(f1, Stroka);
      ModifStr(Stroka, NewStroka);
      writeln(f2, NewStroka);
    end;
  close(f1);
  close(f2);
End.