对于队列的定义,前人之述备矣。
队列的实现方法与栈非常相似。我直接在我实现的那个栈的代码上加了一点东西,全局替换了一些标识符,就实现了这个队列。
我实现的是一个queue
主要的实现思路是,先写出几个支持基本操作的类_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 }
原文链接: https://www.cnblogs.com/jt2001/p/queue20150811.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/220437
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!