Advertisement
OIQ

Untitled

OIQ
Oct 10th, 2021
780
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.30 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. int HandleCommand(const std::string &command, Deque<int> *deque) {
  136.     if (command == "push_back") {
  137.         int number;
  138.         std::cin >> number;
  139.         deque->push_back(number);
  140.         std::cout << "ok\n";
  141.     } else if (command == "push_front") {
  142.         int number;
  143.         std::cin >> number;
  144.         deque->push_front(number);
  145.         std::cout << "ok\n";
  146.     } else if (command == "pop_back") {
  147.         if (deque->empty()) {
  148.             std::cout << "error\n";
  149.         } else {
  150.             std::cout << deque->pop_back() << "\n";
  151.         }
  152.     } else if (command == "pop_front") {
  153.         if (deque->empty()) {
  154.             std::cout << "error\n";
  155.         } else {
  156.             std::cout << deque->pop_front() << "\n";
  157.         }
  158.     } else if (command == "back") {
  159.         if (deque->empty()) {
  160.             std::cout << "error\n";
  161.         } else {
  162.             std::cout << deque->back() << "\n";
  163.         }
  164.     } else if (command == "front") {
  165.         if (deque->empty()) {
  166.             std::cout << "error\n";
  167.         } else {
  168.             std::cout << deque->front() << "\n";
  169.         }
  170.     } else if (command == "size") {
  171.         std::cout << deque->size() << "\n";
  172.     } else if (command == "clear") {
  173.         deque->clear();
  174.         std::cout << "ok\n";
  175.     } else if (command == "exit") {
  176.         std::cout << "bye\n";
  177.         return 0;
  178.     } else {
  179.         std::cout << "invalid command";
  180.         return 0;
  181.     }
  182.  
  183.     return 1;
  184. }
  185.  
  186. int main() {
  187.     Deque<int> deque;
  188.  
  189.     std::string command;
  190.     int result;
  191.  
  192.     do {
  193.         std::cin >> command;
  194.         result = HandleCommand(command, &deque);
  195.     } while (result > 0);
  196.  
  197.     return 0;
  198. }
  199.  
Advertisement
RAW Paste Data Copied
Advertisement