queue概述

queue是一种先进先出(First In First Out, FIFO)，它有两个入口，但只允许在一个入口(队尾)添加元素，在另一个入口(队头)获取和删除元素

queue不允许有遍历行为，所以不提供迭代器

queue
queue

通常使用deque来作为queue的底层实现，这种修改接口的方法被称为适配器模式

因此queue往往不归类为container（容器），而被归类为container adapter（容器适配器）

STL的实现中，可以通过模板参数修改queue的底层容器

queue实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template <typename T, typename Container = Deque<T>>
class Queue {
 public:
  using container_type = Container;
  using value_type = typename Container::value_type;
  using size_type = typename Container::size_type;
  using reference = typename Container::reference;
  using const_reference = typename Container::const_reference;

  template <typename T_, typename Container_>
  friend bool operator==(const Queue<T_, Container_>& lhs, const Queue<T_, Container_>& rhs);
  template <typename T_, typename Container_>
  friend bool operator<(const Queue<T_, Container_>& lhs, const Queue<T_, Container_>& rhs);

  Queue() = default;
  explicit Queue(const Container& c) : c_(c) {}
  explicit Queue(Container&& c) : c_(std::move(c)) {}
  template <typename InputIt, typename Category = typename std::iterator_traits<InputIt>::iterator_category>
  Queue(InputIt first, InputIt last) : c_(first, last) {}
  ~Queue() = default;

  // Element access
  reference front() { return c_.front(); }
  const_reference front() const { return c_.front(); }
  reference back() { return c_.back(); }
  const_reference back() const { return c_.back(); }

  // Capacity
  bool empty() const { return c_.empty(); }
  size_type size() const { return c_.size(); }

  // Modifiers
  void push(const T& v) { c_.push_back(v); }
  void push(T&& v) { c_.push_back(std::move(v)); }
  template <typename... Args>
  void emplace(Args&&... args) {
    c_.emplace_back(std::forward<Args>(args)...);
  }
  template <typename InputIt, typename Category = typename std::iterator_traits<InputIt>::iterator_category>
  void push(InputIt first, InputIt last) {
    for (; first != last; ++first) {
      emplace(*first);
    }
  }
  void pop() { c_.pop_front(); }
  void swap(Queue& other) { std::swap(c_, other.c_); }

 private:
  Container c_;
};  // class Queue

参考