4_6.md

4.6 queue

4.6.1 queue 概述

queue 是一种先进先出的数据结构。它有两个出口。queue 允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了从最底端加入元素、最顶端取出元素外，没有其他方法可以存取 queue 的其他元素。

将元素推入 queue 的操作称为 push，将元素推出 queue 的操作称为 pop。

4.6.2 queue 定义完整列表

SGI STL 以 deque 为底部结构，将其接口改变，使其符合先进先出的特性，形成一个 queue。

template <class T, class Sequence = deque<T>>
class queue {
  // 以下的 __STL_NULL_TEMPL_ARGS 会展开为 <>
  friend bool operator==__STL_NULL_TMPL_ARGS (const queue&, const queue&);
  friend bool operator<__STL_NULL_TMPL_ARGS (const queue&, const queue&);
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: 
  // 以下完全利用 Sequence c 的操作，完成 queue 的操作
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  // deque 是两头可进出，queue 是末端进、前端出
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_front(); }
};

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;
}

4.6.3 queue 没有迭代器

queue 所有元素都必须符合“先进先出”的条件，只有 queue 顶端的元素，才有机会被外界取用。queue 不提供遍历功能，也不提供迭代器。

4.6.4 以 list 作为 queue 的底层容器

若以 list 为底部结构并封闭其某些接口，一样能够轻松形成一个 queue。下面是做法示范：

// file: 4queue-test.cpp
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>

int main() {
  std::queue<int, std::list<int>> iqueue;
  iqueue.push(1);
  iqueue.push(3);
  iqueue.push(5);
  iqueue.push(7);

  std::cout << iqueue.size() << std::endl;    // out: 4
  std::cout << iqueue.front() << std::endl;   // out: 1

  iqueue.pop(); std::cout << iqueue.front() << std::endl;   // out: 3
  iqueue.pop(); std::cout << iqueue.front() << std::endl;   // out: 5
  iqueue.pop(); std::cout << iqueue.front() << std::endl;   // out: 7
  std::cout << iqueue.size() << std::endl;    // out: 1
}