Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 71 стр.

            .        Практикум по курсу «Алгоритмизация и программирование». Часть 2
    Для хранения очереди создается структура, хранящая адреса начала и
конца списка. Это необходимо, так как добавление и извлечение происходит с
разных сторон очереди.
    // структура очереди
    struct Queue
    {
          Node* head;  // указатель на начало очереди
          Node* tail;  // указатель на конец очереди
    };

    При добавлении элемента в очередь приходится отдельно рассматривать
ситуацию, когда очередь пуста. В этом случае нужно формировать ее начало
и конец – они будут указывать на единственный элемент очереди.
    Если же в очереди имеются элементы, то новый добавляется в конец (q.-
tail->next=new Node), и конец очереди сдвигается.

    // определение функции добавления в очередь нового элемента
    void PushQueue(Queue& q, int key)
    {
          if(q.head==NULL)
          {
               q.head=q.tail=new Node;
               q.head->info=key;
               q.head->next=NULL;
               return;
          }
          q.tail->next=new Node;
          q.tail=q.tail->next;
          q.tail->info=key;
          q.tail->next=NULL;
    }

    Если необходимо извлечь элемент из очереди, надо формировать код воз-
врата, который будет равен -1, если очередь пуста, и 1 – в противном случае.
Извлекаемое из очереди значение будет возвращаться через параметр функ-
ции n.
    Из очереди всегда извлекается первый элемент. Поэтому его значение
сохраняется в параметр n, а затем он удаляется. Началом очереди становится
следующий элемент списка. Если в очереди был один элемент (после удале-
ния q.head=NULL), то одновременно обнуляется и q.tail.


                                       71