0x05 栈与队列#

What I cannot create, I do not understand.

—Richard Feynman

备注

栈（Stack） 和 队列（Queue） 是两种很常见的数据结构， 它们都是顺序容器的变体（或如下所说的对底层容器的一种“适配”），只允许在一端进行插入和删除操作。区别在于：

  • 栈先进后出（Last In First Out, LIFO），只允许在栈顶进行插入和删除操作；

  • 队列先进先出（First In First Out, FIFO），只允许在队尾进行插入操作，在队首进行删除操作。

插入和删除操作的时间复杂度都是 \(O(1)\)，因此栈和队列都是一种高效的数据结构。

1💡 C++ 标准库中已经实现了栈 std::stack 与队列 std::queue, 但它们的底层容器默认是 std::deque, 这是出于操作效率和迭代器有效性保证等原因的考虑，我们也可以指定使用其它容器作为底层实现，并进行适配。

设计模式之适配器（Adapter）模式

不难发现，栈和队列 1💡 C++ 标准库中已经实现了栈 std::stack 与队列 std::queue, 但它们的底层容器默认是 std::deque, 这是出于操作效率和迭代器有效性保证等原因的考虑，我们也可以指定使用其它容器作为底层实现，并进行适配。 可以基于顺序容器通过适配进行实现， 但是由于它们自身定义的特殊性，同时也需要对底层容器进行一些限制，比如：

  • 栈要求底层容器必须支持在尾部进行插入和删除操作；

  • 队列要求底层容器必须支持在头部和尾部进行插入和删除操作；

  • 尽可能避免多余的接口暴露，选用最合适的底层容器。

双端队列 Deque#

Wikipedia Visualgo Cppreference

双端队列（Deque） （发音为 “deck”）兼具了数组和链表的优点（这当然是有代价的）， 既可以高效地随机访问，又可以高效地在两端插入和删除。 这是因为双端队列的底层实现是由多个连续子数组（subarray）构成的（ 但子数组彼此不连续 ）， 每个子数组也可称为一个缓冲区（buffer），块（block）或节点（node）。 为了定位子数组，维护了一个索引数组（index/map/…），顺序存放指向子数组的指针 2这种存放数据索引而非数据本身的思路，在实现高效数据结构时非常常见。。

  • 子数组的长度 \(m\) 是固定的（fixed），需要时申请内存，直到 Deque 析构前都不用释放；

  • 在任一端进行插入或删除操作都不会导致指向其他元素的指针或引用失效；

  • 支持随机访问，但其效率要低于数组，因为需要先定位到子数组，再在子数组中进行访问。

设计模式之迭代器（Iterator）模式

Deque 并非内存完全连续的容器，因此无法使用裸指针进行完整遍历，而是需要用到迭代器（iterator）。 由 Deque 的迭代器代为完成在非连续的子数组之间的跳转， 使得用户可以从逻辑上认为 Deque 是连续的，这就是迭代器模式的应用。 具体实现请参考 ChaiGO iterator/deque 源码；

阅读 ChaiGO STL::Deque

  • 接口定义在 Deque，具体实现请参考 ChaiGO container/sequence/deque 源码；

  • 相较于 GNU STL 实现，使用了极少的额外内存空间，但是更加简单易懂。

栈 Stack：先进先出#

Wikipedia Visualgo Cppreference

阅读 ChaiGO STL::Stack

  • 接口定义在 Stack，具体实现请参考 ChaiGO container/adapter/stack 源码；

  • 底层容器默认使用 Deque，也可以指定使用其它容器作为底层实现，并进行适配。

  • 虽然使用 Vector 是可行的，但是在底层需要扩容时会具有更大的操作开销：

队列 Queue：先进后出#

Wikipedia Visualgo Cppreference

阅读 ChaiGO STL::Queue

  • 接口定义在 Queue，具体实现请参考 ChaiGO container/adapter/queue 源码；

  • 底层容器默认使用 Deque，也可以指定使用其它容器作为底层实现，并进行适配。