单选题 已知输入序列是1234,则输入受限(仅允许由一端输入)但输出不受限(两端均可输出)的双端队列不可能得到的输出序列是______。
  • A.4231
  • B.1324
  • C.3214
  • D.2341
【正确答案】 A
【答案解析】[解析] 设双端队列的两端为e1和e2,e1端允许输入,e1和e2端都允许输出。若在e1端输出,相当于栈;若在e2端输出,相当于队列。
对于选项A(4231),要求先输出4,有一种进队方案:1e12e13e14e1,然后从e1端输出4,但由于2夹在1和3之间,下一个输出的不可能是2,所以选项A是不可能的输出序列。
对于选项B(1324),一种操作顺序是1e1进1e1出2e1进3e1进3e1出2e1出4e1进4e1出
对于选项C(3214),一种操作顺序是1e1进2e1进3e1进3e1出2e1出1e1出4e1进4e1出
对于选项D(2341),一种操作顺序是1e1进2e1进2e1出3e1进3e1出4e1进4e1出1e1出