题目重点：区分位置访问和查找值，用固定容量环实现两端操作及随机访问，并说明动态扩容摊还成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练index(i)指按从左开始的非负位置读取，不是查找某个value的位置。
- 先给固定正容量环形数组，满时push报OverflowError，空pop报IndexError；支持存None。
- 每次基础操作严格常数个索引/更新，构造O(capacity)；若要求无限动态增长，需另讨论扩容成本。
解题路线
- 普通双链表有O(1)两端操作，但按位置访问要走到第i节点，不能同时凭这一个结构获得O(1)随机索引。动态数组随机访问常量，但左端插入若搬全部元素会线性。
- 环形数组保留head和size，逻辑位置i映射为(head+i)%capacity。head只是逻辑起点，不要求数据按物理下标连续，因此无需每次lpush移动已有元素。
- lpush把head减1取模再写，rpush写head+size取模；lpop读head后前进，rpop读head+size−1。每次改变size并清理弹出的物理槽，以释放对象引用。
- 必须用size区分满和空，不能靠槽位None，因为None是合法值，也不能仅靠head==tail区分。index先检0≤i<size，不能允许落到未占用槽。
- 固定容量时每个操作只做有限算术与一次访问，满足训练O(1)。满容量的失败不修改head/size/内容，保持调用前状态；wrap-around仍用同一映射。
- 动态容量方案可在满时翻倍，将逻辑序复制到新数组并设head=0，后续操作仍正确。此push最坏O(n)，整体几何扩容给摊还O(1)，不能用“平均”偷偷满足严格最坏要求。缩容也须留滞回避免反复震荡。
- 更强的动态最坏保证可设计分块索引或分阶段搬迁，但需明确分配成本、地址模型及两端迁移不变量；不能仅凭双链表或Python deque名字就承诺全部要求。若index其实查值，重复值和位置变化还会引入另一套索引语义。
手动走一遍
容量3：rpush(a),rpush(b),lpop()后head前进；再rpush(c),rpush(d)可能跨回物理槽0，逻辑index0/1/2仍分别b/c/d。再push报满；None可作为正常元素，不标空。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class IndexedDeque:
def __init__(self, capacity):
if type(capacity) is not int or capacity <= 0:
raise ValueError('capacity must be positive')
self._items = [None] * capacity
self._head = self._size = 0
def __len__(self):
return self._size
def index(self, i):
if type(i) is not int or not 0 <= i < self._size:
raise IndexError(i)
return self._items[(self._head + i) % len(self._items)]
def lpush(self, value):
if self._size == len(self._items):
raise OverflowError('full')
self._head = (self._head - 1) % len(self._items)
self._items[self._head] = value
self._size += 1
def rpush(self, value):
if self._size == len(self._items):
raise OverflowError('full')
self._items[(self._head + self._size) % len(self._items)] = value
self._size += 1
def lpop(self):
if not self._size:
raise IndexError('empty')
value = self._items[self._head]
self._items[self._head] = None
self._head = (self._head + 1) % len(self._items)
self._size -= 1
return value
def rpop(self):
if not self._size:
raise IndexError('empty')
position = (self._head + self._size - 1) % len(self._items)
value = self._items[position]
self._items[position] = None
self._size -= 1
return value
复杂度
构造时间/空间O(C)，C为容量；两端push/pop/index与len各O(1)工作时间O(1)额外空间。动态翻倍版push仅摊还O(1)，单次扩容O(n)。查找value本实现O(n)且未提供。
易错点与追问
容易失分的边界
- 把链表随机index称O(1)。
- index查位置与查值混用。
- 用None标空导致合法None错误。
- 动态扩容的摊还界称最坏界。
继续深挖
- 无限增长是否允许摊还复杂度？
- 删除中间位置如何影响位置访问？
- 多线程无锁环需要哪些发布顺序？
- 分块数组怎样定位逻辑位置和释放块？
