若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（ ）。

A. 1234 B. 4132 C. 4231 D. 4213

队列

[tag_link]

正确答案：C

输入序列为 1234，需找出既不能由输入受限双端队列（插入仅在一端，删除可在两端）也不能由输出受限双端队列（删除仅在一端，插入可在两端）得到的输出序列。

• 选项 A（1234）：两种受限队列均可通过顺序插入和删除得到。
• 选项 B（4132）：输入受限队列可通过插入 1,2,3,4 后依次删除后端 4、前端 1、后端 3、前端 2 得到； 输出受限队列无法得到，因为需要插入 4 前队列前端为 1 且后续顺序为 3,2，但无法通过插入 1,2,3 得到所需队列[1,3,2]。
• 选项 C（4231）：输入受限队列中，插入 1,2,3,4 后删除后端 4，队列变为[1,2,3]，2 不在端部，无法直接输出 2 而不先输出 1 或 3； 输出受限队列中，需要插入 4 前队列为[2,3,1]，但无法通过插入 1,2,3 得到该队列。 因此两种队列均无法得到 4231。
• 选项 D（4213）：输入受限队列无法得到（类似 4231 的原因），但输出受限队列可通过插入 1,2,3 得到队列[2,1,3]，再插入 4 前端后依次删除得到 4213。 综上，4231 既不能由输入受限也不能由输出受限双端队列得到。