algorithm - 出列算法

Question

编写四个时间复杂度为 O(1) 的过程，将元素插入到由数组构造的双端队列的两端并从其两端删除元素。

在我的实现中，我维护了 4 个指针front1、rear1、front2、rear2。

您是否有其他算法具有更少的指针和 O(1) 复杂度？请解释。

Answer 1

有两种常见的实现双端队列的方法:

1. Doubly linked list :您实现了一个双向链表，并维护指向列表前端和末尾的指针。很容易在 O(1) 时间内插入和删除链表的开始/结束。
2. 循环动态数组:在这里，您有一个数组，它被视为循环数组(因此 index=arr.length-1 和 index=0 中的元素> 被视为相邻)。
   在此实现中，您持有“头”和“尾”的索引号。将元素添加到“head”是通过索引 head-1 完成的(同时将头部向后移动)，将元素添加到尾部是通过将其写入索引 tail+1。
   这个方法是分摊O(1)，并且比链表实现有更好的常量。然而，这不是“严格的最坏情况”O(1)，因为如果元素数量超过数组的大小，您需要重新分配一个新数组并将元素从旧数组移动到新的那一个。这需要 O(n) 时间(但至少需要在 O(n) 操作之后完成)，因此它是 O(1) 摊销分析，但有时仍会下降到 O(n)。