Advertisement
OIQ

Untitled

OIQ
Oct 10th, 2021
828
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.09 KB | None
  1. #include <iostream>
  2. #include <string>
  3.  
  4. template <typename T>
  5. class Deque {
  6.  private:
  7.     int head, tail;
  8.     int capacity;
  9.     T *deque;
  10.     int s;
  11.  
  12.     bool isFull() {
  13.         return (head == 0 && tail == capacity - 1) || (head == tail + 1);
  14.     }
  15.  
  16.     void expand() {
  17.         T *buffer = new T[capacity];
  18.         int index = 0;
  19.         while (!empty()) {
  20.             buffer[index++] = pop_front();
  21.         }
  22.         delete[] deque;
  23.         deque = new T[capacity * 2];
  24.         capacity *= 2;
  25.         for (size_t i = 0; i < index; i++) {
  26.             push_back(buffer[i]);
  27.         }
  28.     }
  29.  
  30.  public:
  31.     Deque() {
  32.         capacity = 10;
  33.         head = -1;
  34.         tail = 0;
  35.         deque = new T[capacity];
  36.         s = 0;
  37.     }
  38.  
  39.     void push_front(T x) {
  40.         if (isFull()) {
  41.             expand();
  42.         }
  43.         s++;
  44.         if (head == -1) {
  45.             head = 0;
  46.             tail = 0;
  47.         } else if (head == 0) {
  48.             head = capacity - 1;
  49.         } else {
  50.             head--;
  51.         }
  52.         deque[head] = x;
  53.     }
  54.  
  55.     void push_back(T x) {
  56.         if (isFull()) {
  57.             expand();
  58.         }
  59.         s++;
  60.         if (head == -1) {
  61.             head = 0;
  62.             tail = 0;
  63.         } else if (tail == capacity - 1) {
  64.             tail = 0;
  65.         } else {
  66.             tail++;
  67.         }
  68.  
  69.         deque[tail] = x;
  70.     }
  71.  
  72.     bool empty() {
  73.         return head == -1;
  74.     }
  75.  
  76.     T pop_front() {
  77.         s--;
  78.         if (head == tail) {
  79.             int result = deque[head];
  80.             head = -1;
  81.             tail = -1;
  82.             return result;
  83.         } else {
  84.             if (head == capacity - 1) {
  85.                 T result = deque[head];
  86.                 head = 0;
  87.                 return result;
  88.             } else {
  89.                 T result = deque[head];
  90.                 head++;
  91.                 return result;
  92.             }
  93.         }
  94.     }
  95.  
  96.     T pop_back() {
  97.         s--;
  98.         if (head == tail) {
  99.             T result = deque[head];
  100.             head = -1;
  101.             tail = -1;
  102.             return result;
  103.         } else if (tail == 0) {
  104.             tail = capacity - 1;
  105.             return deque[0];
  106.         } else {
  107.             T result = deque[tail];
  108.             tail--;
  109.             return result;
  110.         }
  111.     }
  112.  
  113.     T front() {
  114.         return deque[head];
  115.     }
  116.  
  117.     T back() {
  118.         return deque[tail];
  119.     }
  120.  
  121.     int size() {
  122.         return s;
  123.     }
  124.  
  125.     void clear() {
  126.         delete[] deque;
  127.         tail = 0;
  128.         head = -1;
  129.         s = 0;
  130.         capacity = 10;
  131.         deque = new T[capacity];
  132.     }
  133. };
  134.  
  135. void insertBack(Deque<int> *deque1, Deque<int> *deque2) {
  136.     int num;
  137.     std::cin >> num;
  138.  
  139.     deque2->push_back(num);
  140.     if (deque2->size() > deque1->size()) {
  141.         deque1->push_back(deque2->pop_front());
  142.     }
  143. }
  144.  
  145. void insertMiddle(Deque<int> *deque1, Deque<int> *deque2) {
  146.     int num;
  147.     std::cin >> num;
  148.  
  149.     if (deque1->size() == deque2->size()) {
  150.         deque1->push_back(num);
  151.     } else {
  152.         deque2->push_front(num);
  153.     }
  154. }
  155.  
  156. void remove(Deque<int> *deque1, Deque<int> *deque2) {
  157.     std::cout << deque1->pop_front() << "\n";
  158.     if (deque2->size() > deque1->size()) {
  159.         deque1->push_back(deque2->pop_front());
  160.     }
  161. }
  162.  
  163. void handle(char command, Deque<int> *deque1, Deque<int> *deque2) {
  164.     switch (command) {
  165.         case '+':
  166.             insertBack(deque1, deque2);
  167.             return;
  168.         case '*':
  169.             insertMiddle(deque1, deque2);
  170.             return;
  171.         case '-':
  172.             remove(deque1, deque2);
  173.             return;
  174.         default:
  175.             return;
  176.     }
  177. }
  178.  
  179.  
  180. int main() {
  181.     // делим всех жителей в пробке на две группы.
  182.     // в первом деке всегда будет >= жителей чем во втором.
  183.     Deque<int> deque1;
  184.     Deque<int> deque2;
  185.     int n;
  186.     std::cin >> n;
  187.     char command;
  188.  
  189.     for (int i = 0; i < n; i++) {
  190.         std::cin >> command;
  191.         handle(command, &deque1, &deque2);
  192.     }
  193.  
  194.     return 0;
  195. }
  196.  
Advertisement
RAW Paste Data Copied
Advertisement