C
队列先进先出,按次序出队,按次序入栈,即按1,2,3,4,5,6依次入栈。C选项:3先出栈,则2比1先出栈。
方法一:模拟
A的操作顺序为①①②②①①③③。
B的操作顺序为②①①①①①③。
C无法找到合适的操作序列。
D的操作顺序为②②②②②①③③③③③。
本题选C。
方法二:单调性
由于只能通过栈改变序列中某子串单调性一次,所以输出序列中没有按照先进先出顺序出队的子串一定通过栈要被反转。
A中子串3, 4没有按序出队,被反转成4, 3,正确。
B中子串1没有按序出队,被反转成1,正确。
C中子串1, 2没有按序出队,但没有被反转,错误。
D中子串1, 2, 3, 4, 5, 6没有按序出队,被反转成6, 5, 4, 3, 2, 1,正确。
本题选C。
如果本题加大难度,输入序列为乱序,需要进行元素值和元素下标的一对一映射,写代码需要建立两个键值哈希表,一个键为元素值,值为元素下标,另一个键为元素下标,值为元素值。
登录后提交答案