На этом шаге мы рассмотрим алгоритмы создания и просмотра дека.

    Мы будем моделировать дек с помощью двунаправленного списка без заглавного звена.

    Вначале опишем алгоритм формирования двунаправленного списка без заглавного звена из двунаправленного списка с заглавным звеном, изображенного ниже:

1. "Начальная" позиция:

   
   Рис.1. "Начальная" позиция

2. Исключим заглавное звено из списка:

       q = nd;
       nd = (*nd).sled; 
       (*nd).pred = NULL;
   

   
   Рис.2. Исключение заглавного звена

3. Возврат памяти в кучу и "настройка" указателя на конец дека:

       delete q;
       kd = z;
   

   
   Рис.3. "Настройка" указателя и возврат памяти в кучу

    Очевидно, что суть алгоритма состоит в "отбрасывании" заглавного звена двунаправленного списка.

    Оформим данный алгоритм в виде функции:

void BuiltDeck (node **nd, node **kd)
// Построение дека на базе двунаправленного 
// списка с заглавным звеном.
// *nd - указатель на начало дека.
// *kd - указатель на конец дека.
{
  node *q, *z;
  int el;

  // Построение заглавного звена.
  *nd = new(node);
  z = *nd;
  (**nd).pred =  (**nd).sled = NULL;
  cout<<"Введите последовательность: \n";
  cin>>el;
  while (el!=0)
    { (*z).sled = new(node); 
      (*((*z).sled)).pred = z; z = (*z).sled; 
      (*z).sled = NULL; (*z).elem = el; cin>>el; }
  if ((**nd).sled!=NULL)
    { q = *nd; *nd = (**nd).sled; (**nd).pred = NULL; *kd = z; delete q; }
  else
    { delete *nd; *nd = *kd = NULL;}
}

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

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