数据结构与算法分析】0基础带你学数据结构与算法分析03--队列 (Queue)

前言

Queue 也是一种受限的线性结构，其末尾被称为队尾 (rear)，而头部被称为队首 (front)。向队列中添加元素被称为 入队 (enqueue)，enqueue 只能在队尾操作；从队列中移除元素被称为 出队 (dequeue)，dequeue 只能在队首操作。因此这种数据结构也被称为 先进先出 (First-In First-Out, FIFO)。

 Queue ADT

template <class T>
concept queue =
    requires(T a, const T& b, const typename T::value_type& value) {
    requires swappable;
    requires erasable<typename T::value_type>;
    requires same<typename T::reference, typename T::value_type&>;
    requires same<typename T::const_reference, const typename T::value_type&>;
    requires unsigned<typename T::size_type>;
    { a.empty() } -> boolean;
    { a.size() } -> typename T::size_type;
    { a.front() } -> typename T::reference;
    { b.front() } -> typename T::const_reference;
    { a.back() } -> typename T::reference;
    { b.back() } -> typename T::const_reference;
    a.push(value);
    a.pop();
};

队列的顺序实现

队列本质上是受限的线性表，因此其与 stack 一样可以直接在线性表上做 adaptor，方便快速的实现。但是对于顺序实现的线性表来说，在队首操作时间复杂度为 O(N) ，其代价太高。我们需要优化现有结构，让其操作时间复杂度降为 O(1) 。

循环队列

对线性表的顺序实现进行简单的改进，使用两个指针 start 与 finish 指向队首元素与队尾元素，而数组边界使用 begin 与 end 指示。插入元素时使 finish+1 ，删除时使 start+1 。但是当 finish 到达数组边界时，就会发生问题，无论 start 前是否剩余空位，都不能再添加元素，因为 finish 已到达边界。这种情况被称为 假溢出 。

显然这个小改进并不能满足需求，为了正常使用，我们假设这个数组是头尾相接的循环数组。因此逻辑上的循环数组不用担心假溢出问题，但也需要每次插入、移除元素时需要检查指针是否到达数组边界，如果已在边界则移动到数组的另一边。

现在思考一下真溢出问题，数组被完完全全的填满了，没有可以容纳元素的方法。这样我们不得不申请更大的一块数组，并将其中元素完整复制进去。当生长时需要 O(N) 的时间复杂度完成迁移，并且需要完全按照从 front 到 rear 的顺序进行。 

分块的双端队列

对于循环队列的缺点进行改进，我们将使用一个全新的方式实现顺序存储。具体思路是：将多个相同大小的块数组组合起来，元素可以被存放在多个不连续的块上，但其连续存储。使用两个指针 start 与 finish 分别指向队首元素与队尾元素，对于每个块有单独的指针指向其头结点。

可以看到，由多个相同大小的块组成了整个存储结构，并且元素在其中顺序存储。可以发现有些块指针并没有引用块，在我们需要的时候，我们可以为其请求一个块，这样我们的数据可以持续的向两边生长，而不需要在生长重新拷贝整个结构。

由于其是多个块数组实现的，且元素顺序、连续排列，因此其可以实现 随机访问 ，其迭代器类型为 radom_access_iterator 。至于跨块访问，应该由实现者对其处理，对使用者透明，使用时可以将其逻辑上作为一个大的块。

可以高效的在两端进行插入、移除元素，但由于分块的特性，需要由实现隐藏其底层块。

 分块双端队列的实现

由于分块双端队列的复杂性，我们将详细说明一下其实现细节。

分块双端队列的迭代器

由于迭代器肩负着隐藏底层块结构的作用，并且还要支持随机访问数据。因此迭代器的实现很重要。

template <class Element>
struct iterator {
  Element* cur;    // 迭代器指向的元素
  Element* first;  // 当前元素所在块数组的起始指针
  Element* last;   // 当前元素所在块数组的末尾指针
  Element** node;  // 当前元素所在的块
};

为了进行随机访问，必须确定当前元素所在的块，才能在不同块之间进行随机访问。在进行随机访问的示例中， chunk_capacity 是一个获取每个块数组可以容纳有多少元素的函数，因此确认每个块的末尾边界。而 __set_node 根据 it 当前指向的元素与将步进的块数量，来设置随机访问的目标结点正确的块信息。

template <class Element>
void __set_node(iterator& it, const difference_type& n) {
  it.node += n;
  it.first = *it.node;
  it.last = *it.node + chunk_capacity();
}
template <class Element>
iterator& operator+=(iterator& it, const difference_type& n) {
  difference_type cap = chunk_capacity();
  const difference_type offset = n + (it.cur - it.first);
  if (0 <= offset && offset < chunk_cap) {
    it.cur += n;
  } else {
    const difference_type tmp = offset < 0 ? -((-offset - 1) / cap) - 1 : offset / cap;
    __set_node(it, tmp);
    it.cur = it.first + (offset - tmp * cap);
  }
  return it;
}

视线放在 operator+= 这个函数，offset 用于判断当前结点需要向前或后步进多少个元素，加 it.cur−it.first是为了将相对起点从 cur 移动到当前所在块的开始位置 first。如果 0≤offset≤capacity 则意味着这次随机访问并不会变更所在块，否则需要计算变更到哪一块。仔细判断步进方向与步进大小，向前步进时将移动 （−offset−1）/cap −1 个块，而向后步进时则需要移动 offset/cap​ 个块。最终元素的位置将相对新的起始指针 offset−tmp∗cap 个元素。

这是相对复杂的步进，而其他步进与此差不了多少，就不再举例说明。

分块双端队列的存储结构

在其存储结构中，需要有一个指针指向块指针的数组的首元素，简单的说就是指向指针的指针，没有使用的块指针应该置空 (nullptr 或 NULL)。其中还需要两个 iterator 分别指向队首元素与队尾元素。

template <class Element>
struct Base {
  using iterator = iterator;
  size_t size;
  Element** chunks;
  iterator begin;
  iterator end;
};

尾言

好啦，到这里我们队列的基础知识也就结束了，希望大家都可以理解运用队列‘下期我们向大家介绍串的知识。