Динамические структуры данных: очереди

Динамические структуры данных: очереди 

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).

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

Выделим типовые операции над очередями:

добавление элемента в очередь (помещение в хвост); 

удаление элемента из очереди (удаление из головы); 

проверка, пуста ли очередь; 

очистка очереди.

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

{Язык Pascal}

Unit Spisok2;

Interface 

      Type BT = LongInt; 

           U = ^Zveno; 

           Zveno = Record Inf : BT; N, P: U End; 

      Procedure V_Och(Var First : U; X : BT); 

      Procedure Iz_Och(Var First : U; Var X : BT); 

      Procedure Ochistka(Var First: U); 

      Function  Pust(First : U) : Boolean;

Implementation 

      Procedure V_Och; 

      Var Vsp : U; 

      Begin 

              New(Vsp); 

              Vsp^.Inf := X; 

              If First = Nil then begin Vsp^.N := Vsp; Vsp^.P := Vsp; First := Vsp end 

                             else begin Vsp^.N := First; Vsp^.P := First^.P; First^.P^.N := Vsp; First^.P := Vsp; end; 

      End; 

      Procedure Iz_Och; 

      Var Vsp : U; 

      Begin 

              x:=first^.inf; 

              if First^.p=first 

              then begin 

                         dispose(first); 

                         first:= nil 

                   end 

              else 

                   begin 

                         Vsp := First; 

                         First := First^.N; 

                         First^.P := Vsp^.P; 

                         Dispose(Vsp) 

                   end 

      End; 

      Procedure Ochistka; 

      Var Vsp : BT; 

      Begin 

               While Not Pust(First) Do Iz_Och(First, Vsp) 

      End; 

      Function  Pust; 

      Begin 

          Pust := First = Nil 

      End;

Begin

End.

// Язык С++

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <time.h>

typedef long BT;

struct U{ 

      BT Inf; 

      U *N, *P;};

U *V_Och(U *First, BT X)

{ U *Vsp; 

 Vsp = (U*) malloc (sizeof(U)); 

 Vsp->Inf=X; 

 if (!First) {Vsp->N=Vsp; Vsp->P=Vsp; First=Vsp;} 

 else {Vsp->N=First; Vsp->P=First->P; First->P->N=Vsp; First->P=Vsp;} 

 return First;}

U *Iz_Och(U *First, BT &X)

{ U *Vsp; 

 X=First->Inf; 

 if (First->P==First) {free(First); First=NULL;} 

 else {Vsp=First; First=First->N; First->P=Vsp->P; free(Vsp);} 

 return First;}

int Pust(U *First)

{   return !First;}

U *Ochistka(U *First)

{ BT Vsp; 

 while (!Pust(First)) First=Iz_Och(First, Vsp); 

 return First;

}

Пример. Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5.

Алгоритм решения. Введем три очереди x2, x3, x5, в которых будем хранить элементы, которые соответственно в 2, 3, 5 раз больше напечатанных, но еще не напечатаны. Рассмотрим наименьший из ненапечатанных элементов; пусть это x. Тогда он делится нацело на одно из чисел 2, 3, 5. x находится в одной из очередей и, следовательно, является в ней первым (меньшие напечатаны, а элементы очередей не напечатаны). Напечатав x, нужно его изъять и добавить его кратные. Длины очередей не превосходят числа напечатанных элементов.

{Язык Pascal}

Program Example;

Uses Spisok2;

Var X2, X3, X5 : U; X : BT; I, N : Word;

Procedure PrintAndAdd(T : BT);

Begin 

   If T <> 1 Then Write(T : 6); 

   V_Och(X2, T * 2); V_Och(X3, T * 3); V_Och(X5, T * 5);

End;

Function Min(A, B, C : BT) : BT;

Var Vsp : BT;

Begin 

   If A < B Then Vsp := A Else Vsp := B; 

   If C < Vsp Then Vsp := C; 

   Min := Vsp

End;

Begin 

   X2 := Nil; X3 := Nil; X5 := Nil; 

   Write('Сколько чисел напечатать? '); ReadLn(N); 

   PrintAndAdd(1); 

   For I := 1 To N Do 

   Begin 

X := Min(X2^.Inf, X3^.Inf, X5^.Inf); 

PrintAndAdd(X); 

If X = X2^.Inf Then Iz_Och(X2, X); 

If X = X3^.Inf Then Iz_Och(X3, X); 

If X = X5^.Inf Then Iz_Och(X5, X); 

   End; 

   Ochistka(X2); Ochistka(X3); Ochistka(X5); 

   WriteLn

End.

// Язык С++

#include "spis2.cpp"

void PrintAndAdd(BT T);

BT Min (BT A, BT B, BT C);

U * X2, *X3, *X5;

void main ()

{ BT X; long I, N; 

X2 = NULL; X3 = NULL; X5 = NULL; 

cout << "Сколько чисел напечатать? "; cin >> N; 

PrintAndAdd(1); 

for (I=1;I<=N; I++) 

{ X = Min(X2->Inf, X3->Inf, X5->Inf); 

  PrintAndAdd(X); 

  if (X==X2->Inf) X2=Iz_Och(X2, X); 

  if (X==X3->Inf) X3=Iz_Och(X3, X); 

  if (X==X5->Inf) X5=Iz_Och(X5, X); 

} 

    X2=Ochistka(X2); X3=Ochistka(X3); X5=Ochistka(X5); cout << endl;

}

void PrintAndAdd(BT T)

{ if (T!=1) {cout.width(6); cout << T;} 

     X2=V_Och(X2, T*2); 

     X3=V_Och(X3, T*3); 

     X5=V_Och(X5, T*5);

}

BT Min (BT A, BT B, BT C)

{ BT vsp; 

 if (A < B) vsp=A; else vsp=B; 

 if (C < vsp) vsp=C; 

 return vsp;

}