C++QUEUE(队列)实现

  1 /* Zarathos 2021.1.28.22：00
  2    链式队列
  3    队列是一种首进首出的数据结构，并且只能够进行尾部插入和头部删除。
  4    该代码所展示队列是链式队列，本质与单链表无异，只是限制了相关操作的单链表
  5    2021.1.29.14:06
  6    转为泛型，使用construct来构造节点元素
  7    修改了构造函数和push函数的实现，增加了emplace函数
  8    2021.1.29 16：54
  9    修正了析构函数的循环错误
 10    将pHead头节点置为dummy哨兵，因为本身pHead就不存储任何数据，不如取消为其分配空间，节约内存
 11    修改了isempty()函数的判断方式
 12    修改了一些函数的参数错误
 13    2021.1.29 17：52
 14    继承allocator空基类，用Getalloc代替al,节约内存....
 15    ########################
 16    美中不足：与STL实现差距过大，无底层容器
 17 */
 18 #ifndef QUEUE_H
 19 #define QUEUE_H
 20 #include <iostream>
 21 #include <memory>
 22 template <typename T> //泛型
 23 struct NODE
 24 {
 25     NODE *pNext;                                                                      //指针域
 26     T data;                                                                           //数据域
 27     NODE(T data = {}, NODE *pNext = nullptr) : data(std::move(data)), pNext(pNext) {} //配合allcator_traits的construct使用的构造函数
 28 };                                                                                    //节点数据类型
 29 template <typename T, typename Alloc = std::allocator<NODE<T>>>
 30 class QUEUE : private Alloc
 31 {
 32 private:
 33     NODE<T> dummy{};         //头节点
 34     NODE<T> *pRear = &dummy; //尾节点
 35     int length;              //长度
 36     Alloc &getalloc()
 37     {
 38         return static_cast<Alloc &>(*this);
 39     }
 40 
 41 public:
 42     QUEUE()
 43     {
 44         pRear->pNext = nullptr;
 45         length = 0;
 46     }
 47     QUEUE(T val)
 48     {
 49         NODE<T> *pNew = getalloc().allocate(1);                                    //新节点分配空间
 50         std::allocator_traits<Alloc>::construct(getalloc(), pNew, std::move(val)); //参数一为分配器，参数二为被构造对象，第三个是值
 51         pRear = pRear->pNext = pNew;
 52         length = 1;
 53     }
 54     QUEUE(const int size, T val)
 55     {
 56         for (unsigned int i = 0; i < size; i++)
 57         {
 58             NODE<T> *pNew = getalloc().allocate(1);
 59             std::allocator_traits<Alloc>::construct(getalloc(), pNew, std::move(val));
 60             pRear = pRear->pNext = pNew;
 61         }
 62         length = size;
 63     }
 64     QUEUE(std::initializer_list<T> Args)
 65     {
 66         for (auto &&p : Args)
 67         {
 68             NODE<T> *pNew = getalloc().allocate(1);
 69             std::allocator_traits<Alloc>::construct(getalloc(), pNew, std::move(p));
 70             pRear = pRear->pNext = pNew;
 71         }
 72         length = Args.size();
 73     }
 74     QUEUE(QUEUE &rhs)
 75     {
 76         dummy = rhs.dummy;
 77         pRear = rhs.pRear;
 78         length = rhs.length;
 79     }
 80     QUEUE(QUEUE &&rhs)
 81     {
 82         dummy = std::move(rhs.dummy);
 83         pRear = std::exchange(rhs.pRear, nullptr);
 84         length = std::exchange(rhs.length, 0);
 85     }
 86     bool is_empty()
 87     {
 88         return !dummy.pNext; //如果dummy.pNext==nullptr返回true,反之返回false(!dummy.pNext==dummy.pNext==nullptr)
 89     }
 90     void show()
 91     {
 92         if (is_empty())
 93         {
 94             printf("The Queue is empty");
 95             return;
 96         }
 97         else
 98         {
 99             NODE<T> *pTemp = dummy.pNext;
100             while (pTemp)
101             {
102                 std::cout << pTemp->data;
103                 pTemp = pTemp->pNext;
104             }
105             printf("\n");
106         }
107     }
108     int size()
109     {
110         return length; //返回长度
111     }
112     int back()
113     {
114         return pRear->data; //返回尾节点元素
115     }
116     int front()
117     {
118         return dummy.pNext->data; //返回第一个元素
119     }
120     void push(T val) //在尾部添加元素
121     {
122         NODE<T> *pNew = getalloc().allocate(1); //分配新节点
123         std::allocator_traits<Alloc>::construct(getalloc(), pNew, std::move(val));
124         pRear = pRear->pNext = pNew; //将新节点与原尾节点产生逻辑关系，同时让尾指针移动到新节点处
125         length++;
126     }
127     template <typename... Args>
128     void emplace(Args &&...args)
129     {
130         NODE<T> *pNew = getalloc().allocate(1);
131         std::allocator_traits<Alloc>::construct(getalloc(), pNew, std::forward<Args>(args)...);
132         pRear = pRear->pNext = pNew;
133         length++;
134     }
135     void pop()
136     {
137         if (is_empty())
138         {
139             return; //为空直接返回
140         }
141         else
142         {
143             if (dummy.pNext == pRear) //第一个元素节点就是尾节点时
144             {
145                 getalloc().destroy(pRear);
146                 pRear = &dummy;        //将尾指针重新指向头节点
147                 dummy.pNext = nullptr; //头节点下一个元素置空
148                 length--;              //长度-1
149                 return;
150             }
151             auto del = dummy.pNext;           //留存第一个元素的地址
152             dummy.pNext = dummy.pNext->pNext; //让第二个元素节点移到第一个的位置
153             getalloc().destroy(del);          //删除原第一个元素节点
154             length--;                         //长度--;
155             return;
156         }
157     }
158     void swap(QUEUE &rhs)
159     {
160         std::swap(dummy, rhs.dummy);
161         std::swap(this->pRear, rhs.pRear);
162         std::swap(this->length, rhs.length);
163     }
164     QUEUE &operator=(QUEUE rhs)
165     {
166         swap(rhs); //交换复制技术
167         return *this;
168     }
169     ~QUEUE()
170     {
171         while (!is_empty()) //如果不为空，一直进行头部删除
172         {
173             pop();
174         }
175     };
176 };
177 #endif