• Списки



• Стеки



• Очереди



• Деревья

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

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

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

• добавление элемента в очередь (помещение в хвост);
• удаление элемента из очереди (удаление из головы);
• проверка, пуста ли очередь;
• очистка очереди.

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

// файл spis2.h

#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;
       First->P->N = Vsp;
       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, нужно его изъять и добавить его кратные. Длины очередей не превосходят числа напечатанных элементов.

#include "spis2.h"
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. Составьте и решите задачу с использованием абстрактного типа данных "очередь".