双端队列

定义

双端队列允许在两端插入和删除元素。它比普通 队列 更灵活，也能模拟 栈 的行为。

受限双端队列

常考两种变形：

  • 输入受限双端队列：只允许从一端插入，允许从两端删除。
  • 输出受限双端队列：允许从两端插入，只允许从一端删除。

与栈、队列的关系

  • 只在一端插入和删除时，双端队列表现得像栈。
  • 固定一端插入、另一端删除时，双端队列表现得像队列。
  • 普通栈的合法输出序列，在相应的双端队列模型中通常仍合法，但双端队列还可能产生更多序列。

判断输出序列

双端队列输出序列题不能直接套 卡特兰数。应根据题目限制模拟两端操作：

  1. 确认哪一端允许插入。
  2. 确认哪一端允许删除。
  3. 按目标输出序列逐个判断当前两端是否能得到目标元素。
  4. 若需要继续输入，按输入顺序加入允许插入的一端。

易错点

  • “输入受限”和“输出受限”是按插入、删除权限命名，不是按队头队尾命名。
  • 普通队列、栈、双端队列都是受限线性表，但限制不同，合法序列集合也不同。