Очередь
Очередь — структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит с одной стороны последовательности, удаление — с другой. Т. е. работает по принципу FIFO (First-In, First-Out).
Содержание
Очередь является динамической структурой — с течением времени изменяется и количество, и набор составляющих ее элементов.
Опишем очередь на языке программирования:
1 2 3 4 5 6 |
Type EXO = ^O; O = record Data : integer; Next : EXO; end; |
Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.
Операции над очередью
В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:
1 2 |
Var BeginO, EndO : EXO; |
где BeginO – соответствует началу очереди и будет использоваться для удаления элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.
Занесение элемента в очередь
Занесение элемента в очередь реализуется как добавлению элемента в конец списка. Рассмотрите процедуру, описанную ниже.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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; |
Извлечение элемента из очереди
Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка. Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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; |
Рассмотрим работу с очередью на примере:
За один просмотр файла действительных чисел напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
Program Cherga; 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); 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 Print(BeginO : EXO); 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; 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('Числа, меньшие ', a); Print(Min); writeln('Числа из промежутка [', a, ',' , b, ']'); Print(Vibr); writeln('Числа, большие ', b); Print(Other); End. |
Практическая часть
Заполнить массив 5х5 случайными числами. Создать очередь из элементов массива, причем чтобы начало очереди содержало среднее арифметическое элементов массива. Вывести очередь на экран.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
Program Cherga2; const n=5; {описание компонент очереди} type List=^Tlist; Tlist=record data:real;{тип елеменетов в очереди} next:List;{указатель на следующий элемент} end; var a:array[1..n,1..n] of real; sr,c:real; i,j:byte; pbegin,pend,u:List;{переменные типа указатель-начало, конец и вспомогательная} begin randomize; {создаем массив и находим в нем среднее} sr:=0; writeln('Исходный массив:'); for i:=1 to n do begin for j:=1 to n do begin a[i,j]:=10*random; sr:=sr+a[i,j]; write(a[i,j]:5:2); end; writeln; end; sr:=sr/(n*n); writeln('Среднее=',sr:0:2); {создаем очередь из одного элемента-среднее} new(pbegin); pbegin^.next:=nil; pbegin^.data:=sr; pend:=pbegin; {добавляем в конец очереди элементы массива} for i:=1 to n do for j:=1 to n do begin new(u); u^.next:=nil; pend^.next:=u; pend:=u; pend^.data:=a[i,j]; end; {выводим элементы очереди на экран} for i:=1 to n*n+1 do begin c:=pbegin^.data; write(c:5:2); pbegin:=pbegin^.next; end; readln end. |