[C++][数据结构]栈(stack)的实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

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

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

我实现的copy structurion其实是用的一个包装了的友元函数_stack_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 stack {
 9   template <class v>
10   friend void _stack_copy(stack<v>& dst, const stack<v>& src);
11 
12 private:
13   struct _stack_impl;
14   _stack_impl *_impl = nullptr;
15   size_t _siz;
16 
17   void _init_empty() {
18     _siz = 0;
19     if (_impl) delete _impl;
20     _impl = new _stack_impl;
21   }
22 
23   void _destory() { _siz = 0; delete _impl; }
24 
25 public:
26   stack() { _init_empty(); }
27   stack(const stack<value> &o) { _stack_copy(*this, o); }
28   ~stack() { _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::stack::pop() - Empty Stack");
37     --_siz; return _impl->pop();
38   }
39 
40   bool empty() const { return _siz == 0; }
41 
42   value top() const {
43     if (_siz == 0)
44       throw std::out_of_range("jt::stack::top() - Empty Stack");
45     return _impl->n->val;
46   }
47 };
48 
49 template <class value>
50 static void _stack_copy(stack<value> &dst, const stack<value> &src) {
51   dst._init_empty();
52   auto **dn = &dst._impl->n; // dest node
53 
54   for (auto *s = src._impl->n; s; s = s->next) {
55     *dn = new typename stack<value>::_stack_impl::node;
56     (*dn)->val = s->val;
57     dn = &(*dn)->next;
58   }
59 
60   dst._siz = src._siz;
61 }
62 
63 template <class value>
64 struct stack<value>::_stack_impl {
65   struct node {
66     value val;
67     node *next = nullptr;
68   } *n = nullptr; // head/top
69 
70   ~_stack_impl() {
71     while (n) {
72       auto *tmp = n->next;
73       delete n;
74       n = tmp;
75     }
76   }
77 
78   void push(const value &val) {
79     node *t = new node;
80     t->val = val;
81     t->next = n;
82 
83     n = t;
84   }
85 
86   value pop() {
87     value v = n->val;
88 
89     node *tmp = n->next;
90     delete n;
91     n = tmp;
92 
93     return v;
94   }
95 };
96 
97 }