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

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура 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;

}

Контрольные вопросы и задания

1. Какую структуру данных называют очередью? Что такое хвост и голова очереди?

2. На базе каких структур данных может быть организована очередь?

3. Приведите из жизни примеры организации чего-либо по принципу очереди.

4. Используя очередь, напечатайте сначала русские символы данной строки, а затем все остальные, сохранив их порядок следования.

5. Составьте и решите задачу с использованием абстрактного типа данных " очередь".