SHARE
TWEET

C++ Queue example

Ver5us May 23rd, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. /*------------------------------------------------------------------- СТЭК ---------------------------------------------------------------*/
  7.  
  8. /*
  9. Тип данных для очереди целых чисел Queue (первый пришёл - первый ушёл).
  10. Тип данных очереди основывается на другом типе данных - Линейный список LinearList:
  11. @data - значение целого числа в узле
  12. @next - указатель на следующий узел (nullptr, если это последний элемент списка)
  13. */
  14. struct LinearList
  15. {
  16.     int data;                           // поле данных
  17.     LinearList* next;                   // указатель на следующий элемент списка
  18. };
  19.  
  20. // но сама очередь по сути - пара указателей на первый и последний элементы списка.
  21.  
  22. struct Queue
  23. {
  24.     LinearList* first;                  // указатель на первый элемент очереди
  25.     LinearList* last;                   // указатель на последний элемент очереди
  26. };
  27.  
  28.  
  29. /*
  30. Операции над очередью Queue -----------------------
  31. В линейном списке мы использовали для доступа к оригинальному списку двойной указатель LinearList**, т.е. указатель на указатель на наш тип данных - вроде как (LinearList*)*,
  32. это было необходимо для того, чтобы в наших функциях можно было менять исходный список.
  33. Здесь используем альтернативный подход: будем прямо в функции явно ждать адрес передаваемого указателя (Queue* &que)
  34. Теперь чтобы менять исходные данные, нам можно передавать их в функцию как обычную переменную, что упрощает читабельность кода.
  35. */
  36.  
  37. // инициализация очереди
  38. void initQueue(Queue* &que)
  39. {
  40.     que = new Queue;                            // выделение памяти
  41.     que->first = nullptr;                       // ...и инициализация конца и начала очереди que нулями (пустыми указателями NULL)
  42.     que->last = nullptr;
  43. }
  44.  
  45. // проверка очереди на пустоту (очередь инициализирована, т.е. память выделена, а начало и конец очереди - пустые)
  46. bool isEmptyQueue(Queue* que)
  47. {
  48.     return ((que != nullptr) && (que->first == nullptr) && (que->last == nullptr));
  49. }
  50.  
  51. // постановка в очередь нового элемента списка со значением value
  52. void enQueue(Queue* &que, const int value)
  53. {
  54.     if (isEmptyQueue(que))                      // если очередь пуста
  55.     {
  56.         que->first = new LinearList;            // создаем новый элемент списка в качестве первого элемента очереди (que->first)
  57.         que->first->data = value;               // и заполняем его данными
  58.         que->first->next = nullptr;
  59.         que->last = que->first;                 // приравнивам последний элемент очереди к свежесозданному первому
  60.     }
  61.     else                                        // ...если же в очереди что-то есть
  62.     {
  63.         LinearList* e = new LinearList;         // созадем новый элемент списка e
  64.         e->data = value;                        // заполняем его данными
  65.         e->next = nullptr;
  66.         que->last->next = e;                    // обновляем последний элемент очереди (добавляем новый элемент в конец)
  67.         que->last = e;                          // смещаем указатель конца очереди que->last на новый элемент
  68.     }
  69. }
  70.  
  71. // извлечение из очереди целочисленного значения
  72. int deQueue(Queue* &que)
  73. {
  74.     //cout << que->first << " [" << que->first->data << "]" << endl;
  75.     LinearList* tmp = que->first;               // создаем временную переменную для хранения указателя на извлекаемый элемент списка (для последующего освобождения памяти)
  76.     int result = que->first->data;              // переменная для извлечения значения первого элемента очереди
  77.    
  78.     if(que->first != que->last)                 // если в очереди осталось больше одного элемента
  79.     {
  80.         que->first = que->first->next;          // смещаем указатель на первый элемент очереди дальше по списку
  81.     }
  82.     else                                        //...если остался один элемент
  83.     {
  84.         que->first = que->first->next;          // сдвигаем указатель на первый элемент дальше (на NULL)
  85.         que->last = que->first;                 // ...и приравниваем к нему указатель на последний элемент
  86.     }
  87.     delete tmp;                                 // чистим память, возвращаем результат извлечения
  88.     return result;
  89. }
  90.  
  91. // Последовательный вывод содержимого линейного списка root (здесь нам не надо менять исходный список, поэтому можно обойтись простым указателем на первый элемент списка LinearList*)
  92. void printLinearList(LinearList* root)
  93. {
  94.     LinearList* e = root;                       // создаем временную переменную e для движения по списку от положения root
  95.     while (e != nullptr)                        // пока не достигнут конец списка, т.е. пока временная переменная e не приняла значение равное пустому указателю nullptr
  96.     {
  97.         std::cout << "[" << e->data << "] -> "; // выводим данные из узла списка @data
  98.         e = e->next;                            // ...и переходим к следующему узлу, сдвигая временный указатель e дальше по списку.
  99.     }
  100.     std::cout << "NULL" << endl;                // конец списка у нас всегда указывает на nullptr (NULL)
  101. }
  102.  
  103. // вывод элементов очереди
  104. void printQueue(Queue* que) {
  105.     std::cout << endl << "Очередь:" << endl;
  106.     printLinearList(que->first);                // по сути эта функция - обертка над выводом элементов списка
  107. }
  108.  
  109. // Создание очереди que и инициализация её значениями на основе массива values длины length
  110. void createQueue(Queue* &que, int* values, const int length)
  111. {
  112.     if (isEmptyQueue(que))                      // если очередь инициализирована и пуста
  113.     {
  114.         for (int i = 0; i < length; i++)        // в цикле по массиву
  115.         {
  116.             enQueue(que, values[i]);            // ставим элементы в очередь
  117.         }
  118.     }
  119. }
  120.  
  121. // Очищаем очередь от элементов
  122. void clearQueue(Queue* &que)
  123. {
  124.     while (!isEmptyQueue(que))                  // пока очередь не опустеет
  125.     {
  126.         deQueue(que);                           // извлекаем элемент из очереди (сдвигая очередь к началу)
  127.     }
  128. }
  129.  
  130.  
  131.  
  132. //-------------------------------------------------------------------------------//
  133. // Задача 3 лабораторной (по варианту 1)
  134. //-------------------------------------------------------------------------------//
  135. void operateQueue(Queue* &que)
  136. {
  137.     cout << endl;
  138.     cout << "------------------------------------------------------" << endl;
  139.     cout << " Определение количества положительных значений элементов очереди: " << endl;
  140.     cout << "------------------------------------------------------" << endl;
  141.  
  142.     int num = 0;                                // количество найденных положительных элементов
  143.  
  144.     if (isEmptyQueue(que))
  145.     {
  146.         cout << "Очередь пуста...";
  147.         return;
  148.     }
  149.  
  150.     cout << "Положительные значения:" << endl;
  151.     while (!isEmptyQueue(que))                  // пока очередь не закончилась
  152.     {
  153.         int pop = deQueue(que);             // извлеваем верхнее значение...
  154.         if (pop > 0)                        // проверяем нечетность значения, извлеченного из стэка
  155.         {
  156.             cout << pop << endl;
  157.             num++;                              // ...и подсчитываем количество найденных элементов, удовлетворяющих условиям задачи
  158.         }
  159.     }
  160.  
  161.     if (num > 0)                                // если в результате обхода списка что-то нашлось, значит можно выводить произведение
  162.     {
  163.         cout << "Количество положительных значений = " << num << endl;
  164.     }
  165.     else                                        // иначе считать особо нечего, не делить же 0 на 0...
  166.     {
  167.         cout << "Чисел удовлетворяющим условиям задачи в очереди не найдено" << endl;
  168.     }
  169. }
  170.  
  171.  
  172.  
  173. int main()
  174. {
  175.     setlocale(LC_ALL, "Russian");
  176.  
  177.     const int default_length = 5;                               // длина инициализационного массива
  178.     int default_data[default_length] = { 1, -4, 3, -44, 7 };    // инициализационный массив значений для инициализации структур
  179.  
  180.     Queue* q;                               // переменная для хранения указателя на вершину стэка
  181.     initQueue(q);                           // инициализируем начало и конец очереди
  182.     printQueue(q);
  183.  
  184.     cout << "------------------------------------------------------" << endl;
  185.     cout << " Создание стэка из массива [1,4,3,44,7]: " << endl;
  186.     cout << "------------------------------------------------------" << endl;
  187.     createQueue(q, default_data, default_length);
  188.     printQueue(q);
  189.  
  190.     cout << endl;
  191.     cout << "------------------------------------------------------" << endl;
  192.     cout << " Добавление элемента в очередь: " << endl;
  193.     cout << "------------------------------------------------------" << endl;
  194.  
  195.     int QData = 0;
  196.     cout << "Введите целое число: ";
  197.     cin >> QData;                           // записываем введенное число в переменную
  198.     enQueue(q, QData);
  199.     printQueue(q);
  200.  
  201.     cout << endl;
  202.     cout << "------------------------------------------------------" << endl;
  203.     cout << " Извлечение элемента из очереди: " << endl;
  204.     cout << "------------------------------------------------------" << endl;
  205.     deQueue(q);
  206.     printQueue(q);
  207.  
  208.     // задание лабораторной по варианту 1
  209.     operateQueue(q);
  210.  
  211.     cout << endl;
  212.     cout << "------------------------------------------------------" << endl;
  213.     cout << " ОЧИСТКА всей очереди: " << endl;
  214.     cout << "------------------------------------------------------" << endl;
  215.  
  216.     clearQueue(q);
  217.     printQueue(q);
  218.  
  219.     return 0;
  220. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top