题19

题19

题目

Q:若以 1,2,3,4 作为双端队列的输入序列, 则既不能由输入受限的双端队列得到, 又不能由输出受限的双端队列得到的输出序列是 ( ).
A. 1,2,3,4
B.
C.
D.

分析

A:所谓的输入，或者叫做插入，也就是队尾指针的后移，这个指针在哪一侧也即是，所谓受限
相同的，输出的意思，也就是队列只能从队头出，也就是队头指针的后移

题19 2024-08-25 19.10.15.excalidraw

解

C
使用排除法。
先看可由输入受限的双端队列产生的序列: 设右端输入受限, 1, 2, 3, 4 依次左入,则依次左出可得 ,排除 ;
左出、右出、左出、左出、左出可得到 ,排除 ;
再看可由输出受限的双端队列产生的序列: 设右端输出受限, 1, 2, 3, 4 依次左入、左入、右入、左入, 依次左出可得到 ,排除 。