3.2.4 双端队列.md

↩返回主页

⬅上一节 / 下一节➡

---

3.2.4 双端队列

• 输出序列

  • 连续输入和输出

    输入序列：1, 2, 3, ..., n

    • 栈的输出序列：n, ..., 3, 2, 1

    • 队列的输出序列：1, 2, 3, ..., n

  • 非连续输入和输出

    • 栈的输出序列满足：每一个元素后面所有比它小的元素组成一个递减序列

      合法出栈序列的个数为：C(2n, n)/(n + 1)

---

  双端队列 是允许两端都可以进行入队以及出队操作的队列。

^{这儿前后端没有等级之分，无论哪一端先出都在序列前，后出都在序列后}

  值得注意，双端队列一端的删除和插入操作抹去，就变成了一个栈，两端各抹去一个删除还有插入，就变成了一个队列。

• 两种受限的双端队列

  • 输出受限的双端队列

    
    ^{两端都可以进行插入，但是只有一端能进行删除}

  • 输入受限的双端队列

    
    ^{两端都可以进行删除，但是只有一端能进行插入}

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --