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

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
    // определение функции извлечения элемента из очереди
    int PopQueue(Queue& q, int& n)
    {
          if(q.head==NULL)
               return -1;
          n=q.head->info;
          Node* p=q.head;
          q.head=q.head->next;
          delete p;
          if(q.head==NULL)
               q.tail=NULL;
          return 1;
    }

    Очереди и стеки имеют широкое применение в различных задачах разбо-
ра математических выражений, обхода деревьев и графов.
    Задача 3. Дан односвязный список. Написать функцию, определяющую,
образуют ли его элементы симметричную последовательность.
    Функция будет возвращать значение true, если список является симмет-
ричным, false – в противном случае.
    По определению пустой список является симметричным. Поэтому, если
список пуст, то возвращаем значение true.
    Для проверки симметричности списка нужно проверить на равенство все
пары элементов, равноотстоящих от середины списка. Каждая пара содержит
один элемент из первой половины списка и один – из второй. Элементы пер-
вой половины списка последовательно заносятся в очередь, второй половины
– в стек. Если количество элементов списка будет нечетным, то серединный
элемент будет симметричен сам себе и не будет помещен ни в очередь, ни в
стек.
    Элементы, находящиеся в начале очереди и в вершине стека, образуют
пару расположенных симметрично относительно середины списка элементов.
Поэтому, извлекая элементы из стека и очереди и проверяя их на равенство,
можно определить, симметричен ли заданный список.
    // определение функции проверки симметричности
    // последовательности чисел в односвязном списке
    bool Symmetry(List* head)
    {
          int n=0,a,b;
          if(head==NULL)
          {
               printf("Список пуст!");

                                            72