stack

stack 是栈, 它只允许在元素在栈顶进出, 而且在实现 stack 这个数据结构的时候, 我们发现, 似乎有一个数据结构已经满足了 stack 只允许元素在尾部进出的功能, 就是 deque, 它已经实现了在头尾都允许元素进出的功能, 所以只需要将 deque 封装一下即也就提取出 pop_back, push_back 就行了. 其实, 不只是 deque , 只要是提供了 pop_back, push_back 功能的数据结构即可, list 也提供了这些方法.

由此发现, stack严格来说并不是容器, 它是一底部容器完成其所有的工作, 它只修改了容器的接口, 准确是叫配接器.

stack 源码

stack也满足straits编程规范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class stack {
  friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
  friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;
public:
  bool empty() const { return c.empty(); } //调用容器的 empty()
  size_type size() const { return c.size(); } //调用容器的 size()
  reference top() { return c.back(); } //调用容器的 push_back
  const_reference top() const { return c.back(); }
  // 只封装了 push_back和pop_back 方法, 只对尾进行操作
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_back(); }
};

//调用容器自己的运算符重载方法
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c < y.c;
}

总结

严格来说 stack 是适配器, 就是修改其他容器提供的功能, 同样 queue 也是以 deque 为默认容器的适配器