Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- constexpr int POP_FRONT = 2;
- constexpr int PUSH_BACK = 3;
- int run(const int* commands, int* elements, int size);
- template<class T>
- class DynamicArray;
- template<class T>
- class Queue;
- int main() {
- int n = 0;
- std::cin >> n;
- int* commands = new int[n];
- int* elements = new int[n];
- for (int i = 0; i < n; i++) {
- std::cin >> commands[i] >> elements[i];
- }
- run(commands, elements, n);
- delete[] commands;
- delete[] elements;
- return 0;
- }
- template<class T>
- class DynamicArray {
- public:
- DynamicArray() : arr(nullptr), size(0), capacity(0) {
- append(0);
- remove(size - 1);
- };
- ~DynamicArray() {delete[] arr;};
- T &operator[](int index) { return arr[index];};
- DynamicArray &operator= (const DynamicArray &other) {
- if (this == &other) {
- return *this;
- }
- size = other.size;
- capacity = other.capacity;
- arr = new T[size];
- std::copy(other.arr, other.arr + size, arr);
- return *this;
- }
- void append(T element);
- void remove(int index);
- int get_size() { return size;};
- void print_arr();
- private:
- T* arr;
- int size;
- int capacity;
- int initial_size = 4;
- void grow();
- };
- template<class T>
- void DynamicArray<T>::append(T element) {
- if (size == capacity) {
- grow();
- }
- arr[size] = element;
- size++;
- }
- template<class T>
- void DynamicArray<T>::grow() {
- int new_capacity = std::max(capacity * 2, initial_size);
- T* new_arr = new T[new_capacity];
- std::copy(arr, arr + size, new_arr);
- delete[] arr;
- arr = new_arr;
- capacity = new_capacity;
- }
- template<class T>
- void DynamicArray<T>::print_arr() {
- for (int i = 0; i < size; i++) {
- std::cout << arr[i] << '@';
- }
- std::cout << '\n' << "capacity is: " << capacity << std::endl;
- }
- template<class T>
- void DynamicArray<T>::remove(int index) {
- std::copy(arr + index + 1, arr + size, arr + index);
- size--;
- }
- template <class T>
- class Queue{
- public:
- Queue() : size(4), head(0), tail(0) {};
- ~Queue() {};
- T pop_front();
- void push_back(T element);
- void print_arr() { buffer.print_arr(); };
- bool is_empty() const { return head == tail;};
- private:
- DynamicArray<T> buffer;
- int size;
- int head;
- int tail;
- void grow();
- };
- template<class T>
- void Queue<T>::grow() {
- if (!size) {
- size = 1;
- }
- int new_size = size * 2;
- auto* new_buffer = new DynamicArray<T>;
- *new_buffer = buffer;
- for (int i = 0; head != tail; i++) {
- buffer.append((*new_buffer)[head]);
- head = (head + 1) % size;
- }
- delete new_buffer;
- head = 0;
- tail = size - 1;
- size = new_size;
- }
- template<class T>
- T Queue<T>::pop_front() {
- T element = buffer[head];
- head = (head + 1) % size;
- return element;
- }
- template<class T>
- void Queue<T>::push_back(T element) {
- if ((tail + 1) % size == head) {
- grow();
- }
- buffer[tail] = element;
- tail = (tail + 1) % size;
- }
- int run(const int* commands, int* elements, int size) {
- Queue<int> queue;
- int q_value = -1;
- for (int i = 0; i < size; i++) {
- switch (commands[i]) {
- case POP_FRONT:
- if (!queue.is_empty()) {
- queue.print_arr();
- q_value = queue.pop_front();
- }
- if (q_value != elements[i]) {
- queue.print_arr();
- std::cout << "NO" << std::endl;
- return 0;
- }
- break;
- case PUSH_BACK:
- queue.print_arr();
- queue.push_back(elements[i]);
- break;
- default:
- std::cout << "NO" << std::endl;
- return 0;
- }
- }
- std::cout << "YES" << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement