出列算法
Dequeue algorithm
编写四个 O(1) 时间过程，在由数组构造的双端队列的两端插入和删除元素。
在我的实现中，我维护了 4 个指针 front1,rear1,front2,rear2。
你还有其他指针更少且复杂度为 O(1) 的算法吗？请解释。
双端队列有两种常见的实现方式：
- Doubly linked list：你实现了一个双向链表，并维护指向链表头尾的指针。在
O(1)时间内插入和删除链表的start/end是很容易的。
- 循环动态数组：在这里，你有一个数组，它被视为循环数组（因此 index=
arr.length-1 和 index=0 中的元素被视为相邻）。
在此实现中，您持有 "head" 和 "tail" 的索引号。将元素添加到 "head" 是对索引 head-1 完成的（同时将头部向后移动），将元素添加到尾部是通过将其写入索引 tail+1 来完成的。
这个方法被分摊 O(1)，并且比链表实现有更好的常量。但是，它不是"strict worst case" O(1)，因为如果元素的数量超过数组的大小，则需要重新分配一个新数组并将元素从旧数组移动到新数组。这需要 O(n) 时间（但需要在至少 O(n) 操作后完成），因此它是 O(1) 摊销分析，但仍然会不时下降到 O(n)时间。
编写四个 O(1) 时间过程，在由数组构造的双端队列的两端插入和删除元素。
在我的实现中，我维护了 4 个指针 front1,rear1,front2,rear2。
你还有其他指针更少且复杂度为 O(1) 的算法吗？请解释。
双端队列有两种常见的实现方式：
- Doubly linked list：你实现了一个双向链表，并维护指向链表头尾的指针。在
O(1)时间内插入和删除链表的start/end是很容易的。 - 循环动态数组：在这里，你有一个数组，它被视为循环数组（因此 index=
arr.length-1和 index=0中的元素被视为相邻）。
在此实现中，您持有 "head" 和 "tail" 的索引号。将元素添加到 "head" 是对索引head-1完成的（同时将头部向后移动），将元素添加到尾部是通过将其写入索引tail+1来完成的。
这个方法被分摊O(1)，并且比链表实现有更好的常量。但是，它不是"strict worst case"O(1)，因为如果元素的数量超过数组的大小，则需要重新分配一个新数组并将元素从旧数组移动到新数组。这需要O(n)时间（但需要在至少O(n)操作后完成），因此它是O(1)摊销分析，但仍然会不时下降到O(n)时间。