На этом шаге мы рассмотрим алгоритм формирования очереди.

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

Запишем алгоритм формирования очереди:

    r = new (node);
    (*r).elem = Элем;
    (*r).sled = NULL;

Рис.1. Первый элемент в очереди

```
    no = r; ko = r;
```
Рис.2. Настройка указателей начала и конца очереди

Итак, мы образовали очередь, состоящую из одного звена.
Продолжим заполнение очереди:
```
    r = new (node);
    (*r).elem = Элем1;
    (*r).sled = NULL;
```
Рис.3. Создали новый элемент очереди
Настроим указатель на конец очереди:
```
    (*ko).sled = r; 
    ko = r;
```
Рис.4. Настроили указатель на конец очереди

Таким образом, очередь уже содержит два звена и, нам думается, что процесс построения понятен.

Представим описанный алгоритм в виде функции на языке C++:

void POSTROENIE (node **no, node **ko)
// Построение очереди на базе однонаправленного 
// линейного списка без заглавного звена: 
// *no - указатель на начало очереди, 
// *ko - указатель на конец очереди.
{
  node *r;
  int el;

  cin>>el;
  if (el!=0)
  {
    r = new (node);
    (*r).elem = el;
    (*r).sled = NULL; 
    *no = r; 
    *ko = r;
    cin>> el;
    while (el!=0) 
      { r = new (node);
       (*r).elem = el; (*r).sled = NULL;
       (**ko).sled = r; *ko = r; cin>>el;}
      }
  else
  { r = NULL; *no = r; *ko = r;}
}

Тут же приведем функцию для просмотра содержимого очереди:

void VYVOD (node **no, node **ko)
// Вывод содержимого очереди. 
// *no - указатель на начало очереди, 
// *ko - указатель на конец очереди.
{
  node *r;
  cout<< "Очередь: "; r = *no;
  while (r!=NULL)
    { cout<<(*r).elem<<" "; r = (*r).sled; }
  cout<<endl;
}

Замечание[1, с.52]. Очереди целесообразно хранить в памяти ЭВМ в виде кольцевого списка с двумя указателями (один - на начало, другой - на конец очереди):

Рис.5. Представление очереди

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

⁽¹⁾Разумов О.С. Организация данных в вычислительных системах. - М.: Статистика, 1978. - 184 с.

Со следующего шага мы начнем рассматривать операции с очередями.

Предыдущий шаг Содержание Следующий шаг