queue

queue 是队列, 只允许元素从队首弹出, 在队尾进入, 其也是使用 deque 作为默认容器, 将其功能进行封装得到的,

其可参考 stack

queue 结构

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
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class queue {
  //定义友元函数
  friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
  friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
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(); }
  size_type size() const { return c.size(); }
  // 调用 deque 的 front 方法
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  // 由于只提供前出后入的功能, 所以只封装了 push_back, pop_front函数
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_front(); }
};

友元函数

1
2
3
4
5
6
7
8
9
10
// 实现重载
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
  return x.c == y.c;
}

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

总结

queue与stack都是使用底层接口封装的结构, 他们是被称为配接器而不是容器.