Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.65 KB | None | 0 0
  1. #ifndef _queue_h_
  2. #define _queue_h_
  3.  
  4. #pragma region PresentationAsList
  5. template <typename T>
  6. class QueueAsList {
  7.  
  8. public:
  9.  
  10.     QueueAsList();
  11.     ~QueueAsList();
  12.  
  13.     T pop();
  14.     T front();
  15.     void push(const T& input);
  16.     bool empty();
  17.  
  18. private:
  19.  
  20.     QueueAsList(const QueueAsList& dummy) = delete;
  21.     QueueAsList& operator=(const QueueAsList& dummy) = delete;
  22.  
  23.     struct Elem {
  24.  
  25.         Elem* next;
  26.         T data;
  27.  
  28.     };
  29.  
  30.     Elem* head;
  31.     Elem* tail;
  32.  
  33. };
  34.  
  35. template<typename T>
  36. inline QueueAsList<T>::QueueAsList() {
  37.  
  38.     head = nullptr;
  39.  
  40.     tail = nullptr;
  41.  
  42. }
  43.  
  44.  
  45. template<typename T>
  46. inline QueueAsList<T>::~QueueAsList() {
  47.  
  48.     Elem* curr;
  49.  
  50.     while (head != nullptr) {
  51.  
  52.         curr = head;
  53.         head = head->next;
  54.         delete curr;
  55.  
  56.     }
  57.  
  58. }
  59.  
  60. template<typename T>
  61. inline T QueueAsList<T>::pop() {
  62.  
  63.     if (head == tail) {
  64.  
  65.         T answer = head->data;
  66.         delete head;
  67.         head = nullptr;
  68.         tail = nullptr;
  69.         return answer;
  70.  
  71.     }
  72.  
  73.     Elem* curr = head;
  74.     head = head->next;
  75.     T answer = curr->data;
  76.     delete curr;
  77.     return answer;
  78.  
  79. }
  80.  
  81. template<typename T>
  82. inline T QueueAsList<T>::front() {
  83.  
  84.     return head->data;
  85.  
  86. }
  87.  
  88. template<typename T>
  89. inline void QueueAsList<T>::push(const T& input) {
  90.  
  91.     if (head == nullptr) {
  92.  
  93.         tail = new Elem;
  94.         head = tail;
  95.         head->next = nullptr;
  96.         head->data = input;
  97.         return;
  98.  
  99.     }
  100.  
  101.     tail->next = new Elem;
  102.     tail = tail->next;
  103.     tail->next = nullptr;
  104.     tail->data = input;
  105.  
  106. }
  107.  
  108. template<typename T>
  109. inline bool QueueAsList<T>::empty() {
  110.  
  111.     if (head == nullptr)
  112.         return true;
  113.  
  114.     return false;
  115. }
  116. #pragma endregion
  117.  
  118. #pragma region PresentationAsVector
  119. template <typename T>
  120. class QueueAsVector {
  121.  
  122. public:
  123.  
  124.     QueueAsVector();
  125.     ~QueueAsVector();
  126.  
  127.     void push(const T& input);
  128.     bool empty();
  129.     T front();
  130.     T pop();
  131.  
  132. private:
  133.  
  134.     QueueAsVector(const QueueAsVector& dummy) = delete;
  135.     QueueAsVector& operator=(const QueueAsVector& dummy) = delete;
  136.  
  137.     void decreaseSize();
  138.  
  139.     T* data;
  140.     int head;
  141.     int tail;
  142.     int cap;
  143.     int numberElem;
  144.  
  145. };
  146.  
  147. template<typename T>
  148. inline QueueAsVector<T>::QueueAsVector() {
  149.  
  150.     data = nullptr;
  151.  
  152. }
  153.  
  154. template<typename T>
  155. inline QueueAsVector<T>::~QueueAsVector() {
  156.  
  157.     delete[] data;
  158.  
  159. }
  160.  
  161. template<typename T>
  162. inline void QueueAsVector<T>::push(const T& input) {
  163.  
  164.     if (data == nullptr) {
  165.  
  166.         data = new T[5];
  167.         cap = 5;
  168.         numberElem = 1;
  169.         head = tail = 0;
  170.         data[head] = input;
  171.         return;
  172.  
  173.     }
  174.  
  175.     if (numberElem == cap) {
  176.  
  177.         T* newData = new T[cap * 2];
  178.  
  179.         int curr = head;
  180.         for (int i = 0; i < cap; ++i) {
  181.  
  182.             if (curr == tail) {
  183.  
  184.                 newData[i] = data[curr];
  185.                 break;
  186.  
  187.             }
  188.  
  189.             newData[i] = data[curr];
  190.  
  191.             if (curr == cap - 1)
  192.                 curr = -1;
  193.  
  194.             ++curr;
  195.  
  196.         }
  197.  
  198.         newData[cap] = input;
  199.         head = 0;
  200.         tail = cap;
  201.         ++numberElem;
  202.         cap *= 2;
  203.         delete[] data;
  204.         data = newData;
  205.         return;
  206.  
  207.     }
  208.  
  209.     if (tail == cap - 1)
  210.         tail = -1;
  211.  
  212.     ++tail;
  213.     data[tail] = input;
  214.     ++numberElem;
  215.  
  216. }
  217.  
  218. template<typename T>
  219. inline bool QueueAsVector<T>::empty() {
  220.  
  221.     if (numberElem == 0)
  222.         return true;
  223.  
  224.     return false;
  225.  
  226. }
  227.  
  228. template<typename T>
  229. inline T QueueAsVector<T>::front() {
  230.  
  231.     std::cout << "\n front Current head: " << head << std::endl;
  232.     T answer = data[head];
  233.  
  234.     return answer;
  235.  
  236. }
  237.  
  238. template<typename T>
  239. inline T QueueAsVector<T>::pop() {
  240.  
  241.     std::cout << "\n pop Current head: " << head << std::endl;
  242.     T answer = data[head];
  243.  
  244.     if (head == cap - 1)
  245.         head = -1;
  246.  
  247.     ++head;
  248.     --numberElem;
  249.  
  250.     decreaseSize();
  251.     return answer;
  252.  
  253. }
  254.  
  255. template<typename T>
  256. inline void QueueAsVector<T>::decreaseSize() {
  257.  
  258.     if (cap < 3)
  259.         return;
  260.  
  261.     if (cap * 3 / 4 > numberElem) {
  262.  
  263.         T* newData = new T[cap * 3 / 4];
  264.         int curr = head;
  265.  
  266.         for (int i = 0;; ++i) {
  267.  
  268.             if (curr == tail) {
  269.  
  270.                 newData[i] = data[curr];
  271.                 break;
  272.  
  273.             }
  274.  
  275.             newData[i] = data[curr];
  276.  
  277.             if (curr == cap - 1)
  278.                 curr = -1;
  279.  
  280.             ++curr;
  281.  
  282.         }
  283.  
  284.         head = 0;
  285.         tail = numberElem - 1;
  286.         cap = cap * 3 / 4;
  287.  
  288.         delete[] data;
  289.         data = newData;
  290.  
  291.     }
  292.  
  293. }
  294. #pragma endregion
  295.  
  296. #endif // !_queue_h_
  297.  
  298. #include <iostream>
  299. //----------------------
  300.  
  301.  
  302.  
  303.  
  304. #include <iostream>
  305. //#include "queue.h"
  306.  
  307. int main() {
  308.  
  309.    
  310.     /*QueueAsList <int>test;
  311.     test.push(1);
  312.     std::cout << test.front() << std::endl;
  313.     if (!test.empty())
  314.         std::cout << test.pop() << std::endl;
  315.     test.push(2);
  316.     test.push(3);
  317.     if (!test.empty())
  318.         std::cout << test.pop() << std::endl;
  319.     if (!test.empty())
  320.         std::cout << test.pop() << std::endl;*/
  321.  
  322.     QueueAsVector <int>test;
  323.     int input;
  324.     for (int i = 0; i < 10; ++i) {
  325.  
  326.         //std::cin >> input;
  327.         for(int i=1;i<=10;++i)
  328.             test.push(i);
  329.  
  330.     }
  331.  
  332.     while (!test.empty()) {
  333.  
  334.         std::cout << test.front() << " " << test.pop() << std::endl;
  335.  
  336.     }
  337.  
  338.     return 0;
  339.  
  340. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement