[C++][数据结构]队列(queue)的实现

对于队列的定义，前人之述备矣。

队列的实现方法与栈非常相似。我直接在我实现的那个栈的代码上加了一点东西，全局替换了一些标识符，就实现了这个队列。

我实现的是一个queue<value>容器类，支持push,pop,top,size,empty,clear和copy construction操作。

主要的实现思路是，先写出几个支持基本操作的类_queue_impl，然后再写一个包装类queue，包装基本操作，再实现size,copy struction,top,clear和抛出异常的功能。这样做(pImpl)的好处不言而喻。

我实现的copy structurion其实是用的一个包装了的友元函数_queue_copy(dst, src)，因为这样可以直接访问底部成员并进行复制，比使用用户接口，先一个一个pop，再一个一个push，快多了。

代码使用C++11标准。如果有不对的地方，欢迎指出。

在Win7 mingw32 gcc4.7下编译并测试通过。测试内容非常简单，所以可能会有一些没测试出来的问题。

以下是实现

  1 #pragma once
  2 #include <cstddef>
  3 #include <stdexcept>
  4 
  5 namespace jt {
  6 
  7 template <class value>
  8 class queue {
  9   template <class v>
 10   friend void _queue_copy(queue<v>& dst, const queue<v>& src);
 11 
 12 private:
 13   struct _queue_impl;
 14   _queue_impl *_impl = nullptr;
 15   size_t _siz;
 16 
 17   void _init_empty() {
 18     _siz = 0;
 19     if (_impl) delete _impl;
 20     _impl = new _queue_impl;
 21   }
 22 
 23   void _destory() { _siz = 0; delete _impl; }
 24 
 25 public:
 26   queue() { _init_empty(); }
 27   queue(const queue<value> &o) { _queue_copy(*this, o); }
 28   ~queue() { _destory(); }
 29 
 30   void clear() { _init_empty(); }
 31   void push(const value &val) { _impl->push(val); ++_siz; }
 32   size_t size() const { return _siz; }
 33 
 34   value pop() {
 35     if (_siz == 0)
 36       throw std::out_of_range("jt::queue::pop() - Empty queue");
 37     --_siz; return _impl->pop();
 38   }
 39 
 40   bool empty() const { return _siz == 0; }
 41 
 42   value front() const {
 43     if (_siz == 0)
 44       throw std::out_of_range("jt::queue::front() - Empty queue");
 45     return _impl->f->val;
 46   }
 47 
 48   value back() const {
 49     if (_siz == 0)
 50       throw std::out_of_range("jt::queue::back() - Empty queue");
 51     return _impl->b->val;
 52   }
 53 };
 54 
 55 template <class value>
 56 static void _queue_copy(queue<value> &dst, const queue<value> &src) {
 57   dst._init_empty();
 58   auto **dn = &dst._impl->f; // dest node
 59 
 60   for (auto *s = src._impl->f; s; s = s->next) {
 61     *dn = new typename queue<value>::_queue_impl::node;
 62     (*dn)->val = s->val;
 63     dst._impl->b = *dn;
 64     dn = &(*dn)->next;
 65   }
 66 
 67   dst._siz = src._siz;
 68 }
 69 
 70 template <class value>
 71 struct queue<value>::_queue_impl {
 72   struct node {
 73     value val;
 74     node *next = nullptr;
 75   } *f = nullptr, // front
 76     *b;           // back
 77 
 78   ~_queue_impl() {
 79     while (f) {
 80       auto *tmp = f->next;
 81       delete f;
 82       f = tmp;
 83     }
 84   }
 85 
 86   void push(const value& val) {
 87     node *t = new node;
 88     t->val = val;
 89 
 90     if (f) b->next = t;
 91     else f = t; // if empty, set front
 92 
 93     b = t;
 94   }
 95 
 96   value pop() {
 97     value v = f->val;
 98 
 99     node *tmp = f->next;
100     delete f;
101     f = tmp;
102 
103     return v;
104   }
105 };
106 
107 }