Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.00 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. constexpr int POP_FRONT = 2;
  4. constexpr int PUSH_BACK = 3;
  5.  
  6. int run(const int* commands, int* elements, int size);
  7.  
  8. template<class T>
  9. class DynamicArray;
  10.  
  11. template<class T>
  12. class Queue;
  13.  
  14.  
  15. int main() {
  16.     int n = 0;
  17.     std::cin >> n;
  18.     int* commands = new int[n];
  19.     int* elements = new int[n];
  20.     for (int i = 0; i < n; i++) {
  21.         std::cin >> commands[i] >> elements[i];
  22.     }
  23.  
  24.     run(commands, elements, n);
  25.  
  26.     delete[] commands;
  27.     delete[] elements;
  28.     return 0;
  29. }
  30.  
  31. template<class T>
  32. class DynamicArray {
  33. public:
  34.     DynamicArray() : arr(nullptr), size(0), capacity(0) {
  35.         append(0);
  36.         remove(size - 1);
  37.     };
  38.     ~DynamicArray() {delete[] arr;};
  39.  
  40.     T &operator[](int index) { return arr[index];};
  41.     DynamicArray &operator= (const DynamicArray &other) {
  42.         if (this == &other) {
  43.             return *this;
  44.         }
  45.         size = other.size;
  46.         capacity = other.capacity;
  47.         arr = new T[size];
  48.         std::copy(other.arr, other.arr + size, arr);
  49.         return *this;
  50.     }
  51.  
  52.     void append(T element);
  53.     void remove(int index);
  54.     int get_size() { return size;};
  55.  
  56.     void print_arr();
  57.  
  58. private:
  59.     T* arr;
  60.     int size;
  61.     int capacity;
  62.     int initial_size = 4;
  63.  
  64.     void grow();
  65. };
  66.  
  67.  
  68. template<class T>
  69. void DynamicArray<T>::append(T element) {
  70.     if (size == capacity) {
  71.         grow();
  72.     }
  73.     arr[size] = element;
  74.     size++;
  75. }
  76.  
  77. template<class T>
  78. void DynamicArray<T>::grow() {
  79.     int new_capacity = std::max(capacity * 2, initial_size);
  80.     T* new_arr = new T[new_capacity];
  81.     std::copy(arr, arr + size, new_arr);
  82.  
  83.     delete[] arr;
  84.  
  85.     arr = new_arr;
  86.     capacity = new_capacity;
  87. }
  88.  
  89. template<class T>
  90. void DynamicArray<T>::print_arr() {
  91.     for (int i = 0; i < size; i++) {
  92.         std::cout << arr[i] << '@';
  93.     }
  94.     std::cout << '\n' << "capacity is: " << capacity << std::endl;
  95. }
  96.  
  97. template<class T>
  98. void DynamicArray<T>::remove(int index) {
  99.     std::copy(arr + index + 1, arr + size, arr + index);
  100.     size--;
  101. }
  102.  
  103.  
  104. template <class T>
  105. class Queue{
  106. public:
  107.     Queue() : size(4), head(0), tail(0) {};
  108.     ~Queue() {};
  109.  
  110.     T pop_front();
  111.     void push_back(T element);
  112.     void print_arr() { buffer.print_arr(); };
  113.  
  114.     bool is_empty() const { return head == tail;};
  115.  
  116. private:
  117.     DynamicArray<T> buffer;
  118.     int size;
  119.     int head;
  120.     int tail;
  121.  
  122.     void grow();
  123. };
  124.  
  125. template<class T>
  126. void Queue<T>::grow() {
  127.     if (!size) {
  128.         size = 1;
  129.     }
  130.     int new_size = size * 2;
  131.     auto* new_buffer = new DynamicArray<T>;
  132.     *new_buffer = buffer;
  133.     for (int i = 0; head != tail; i++) {
  134.         buffer.append((*new_buffer)[head]);
  135.         head = (head + 1) % size;
  136.     }
  137.     delete new_buffer;
  138.  
  139.     head = 0;
  140.     tail = size - 1;
  141.     size = new_size;
  142. }
  143.  
  144. template<class T>
  145. T Queue<T>::pop_front() {
  146.     T element = buffer[head];
  147.     head = (head + 1) % size;
  148.     return element;
  149. }
  150.  
  151. template<class T>
  152. void Queue<T>::push_back(T element) {
  153.     if ((tail + 1) % size == head) {
  154.         grow();
  155.     }
  156.     buffer[tail] = element;
  157.     tail = (tail + 1) % size;
  158. }
  159.  
  160.  
  161. int run(const int* commands, int* elements, int size) {
  162.     Queue<int> queue;
  163.  
  164.     int q_value = -1;
  165.     for (int i = 0; i < size; i++) {
  166.         switch (commands[i]) {
  167.             case POP_FRONT:
  168.                 if (!queue.is_empty()) {
  169.                     queue.print_arr();
  170.                     q_value = queue.pop_front();
  171.                 }
  172.                 if (q_value != elements[i]) {
  173.                     queue.print_arr();
  174.                     std::cout << "NO" << std::endl;
  175.                     return 0;
  176.                 }
  177.                 break;
  178.             case PUSH_BACK:
  179.                 queue.print_arr();
  180.                 queue.push_back(elements[i]);
  181.                 break;
  182.             default:
  183.                 std::cout << "NO" << std::endl;
  184.                 return 0;
  185.         }
  186.     }
  187.     std::cout << "YES" << std::endl;
  188.     return 0;
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement