Advertisement
ValeriyZubairov

Задача 4. Очередь с дин. буфером

Mar 25th, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3.  
  4. class queue {
  5.     int *numbers;   //указатель на массив чисел
  6.     int size_of_numb; //размер массива
  7.  
  8.     int head;       // номер первого
  9.     int tail;       // номер последнего
  10.  
  11.  
  12.     void up_size() //Приращение памяти
  13.     {
  14.         int new_size = size_of_numb > 0 ? size_of_numb*1.6 : 10;  //если размер =0, то увеличиваем на 10, иначе в 1.6 раза
  15.         int *new_numbers = new int[new_size];
  16.  
  17.         if (head != tail) {                              //Если начальный массив не пуст            
  18.             int temp = 0;
  19.             for (int i = head; i <size_of_numb; i++) {
  20.                 if (i == tail) {
  21.                     break;
  22.                 }
  23.  
  24.                 new_numbers[temp++] = numbers[i];
  25.  
  26.                 if (i == size_of_numb - 1) {
  27.                     i = -1;
  28.                 }
  29.                 }
  30.             head = 0;
  31.             tail = temp;
  32.         }
  33.  
  34.         if (numbers != NULL) {     //удаление начального массива
  35.             delete[] numbers;
  36.         }
  37.  
  38.         numbers = new_numbers;
  39.         size_of_numb = new_size;
  40.     }
  41.  
  42. public:
  43.     queue() {        
  44.         numbers = NULL;
  45.         size_of_numb = 0;
  46.  
  47.         head = 0;
  48.         tail = 0;
  49.  
  50.         up_size();
  51.     }
  52.  
  53.     ~queue() {
  54.         if (numbers != NULL) {
  55.             delete[] numbers;
  56.         }
  57.     }
  58.  
  59.     //Взятие элемента
  60.     int pop() {
  61.         if (head != tail) {
  62.             // очередь не пуста
  63.             int val = numbers[head];
  64.  
  65.             if (head == size_of_numb - 1) {
  66.                 head = 0;
  67.             }
  68.             else
  69.             {
  70.                 head++;
  71.             }
  72.  
  73.             return val;
  74.         }
  75.  
  76.         // очередь пуста
  77.         return -1;
  78.     }
  79.     // добавление элемента
  80.     void push(int val) {
  81.         if ((tail + 1) % size_of_numb == head) {
  82.             //если размер массива недостаточен
  83.             up_size();
  84.             push(val);
  85.         }
  86.         else
  87.         {
  88.             // добавление
  89.             numbers[(tail) % size_of_numb] = val;
  90.             tail = (tail + 1) % size_of_numb;
  91.         }
  92.     }
  93.  
  94.     bool is_empty() {      //Проверка на пустую очередь
  95.         return head == tail;
  96.     }
  97.  
  98. };
  99.  
  100.  
  101.  
  102. int main()
  103. {
  104.     queue queue_for_task;
  105.  
  106.     int n = -1;      //Количество команд
  107.     std::cin >> n;
  108.     assert(n > 0 && n < 1000000);
  109.     bool is_OK = true;
  110.  
  111.     int command_type = 0;
  112.     int value = 0;
  113.     for (int i = 0; i < n; i++) {
  114.         //Ввод типа команды и значения
  115.         std::cin >> command_type >> value;
  116.         assert(command_type == 2 || command_type == 3);
  117.         switch (command_type) {
  118.         case 2:
  119.             if (queue_for_task.is_empty()) {
  120.                 value = -1;
  121.                 break;
  122.             }
  123.             is_OK = (queue_for_task.pop() == value) && is_OK;
  124.            
  125.             break;
  126.         case 3:
  127.             queue_for_task.push(value);
  128.             break;
  129.         }
  130.     }
  131.     std::cout << (is_OK ? "YES" : "NO");
  132.  
  133.     delete queue_for_task;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement