双端队列，也就是栈和队列的结合，同时可以从头和尾进行进出栈 / 队列的功能，看一下他的数据结构就懂了：
双端队列的实现还是比较简单的（虽然实际上还会是踩了一些微小的坑）。
首先，回忆一下链表和队列的数据结构，有以下几种实现：
链表实现和数组实现的各操作时间复杂度不用赘述，链表对于收尾操作非常轻松，对于随机访问却比较复杂，而数组访问起来简单。
对于这样一个双端队列，我们不需要考虑随机访问的操作，所以选择链表去实现明显是更为合适的。
首先我们要考虑到他需要随机删除队列中的一个数，那么删除时肯定会访问到数列中的随机一个数，因此用数组的实现更好。
在这里，我们假定是随机选择出队，所以入队操作是同样顺序的。在出队上，最初我想着 Random 第 n 个元素出队，结果遇到的麻烦是复杂度不是常数时间，而是线性的，所以我们换了一个方法，将 random 到的元素与最后一个元素交换，这样为空的就永远是最后的元素了，不需要使用循环来探测元素。
在迭代器的构件上，为了保证每个迭代器的元素都不同，我们使用了 shuffle 函数来保证独立的乱序，这样在遍历时只要顺序遍历下去就行了。
如果您觉得文章不错，可以通过赞助支持我。
如果您不希望打赏，也可以通过关闭广告屏蔽插件的形式帮助网站运作。