【软考】数据结构之队列和栈

1.例题一

1.1题目

输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如下图所示，若有e1，e2，e3，e4依次进入输出受限的双端队列，则得不到输出序列()。
A.e4, e3, e2, e1
B.e4, e2, e1, e3
C.e4, e3, e1, e2
D.e4, e2, e3, e1
1
2
3
4
5

1.2 题目截图

1.3 题目分析

• 1.对于1来说，因为是第一个进入，不管从左进还是右进，都一样
• 2.对于2来说，从左进入则是2-1，从右进则是1-2
• 3.在2-1情况下，3若是从左进则是3-2-1，从右进则是2-1-3
• 4.在3-2-1情况下，4若是从左进则是4-3-2-1，从右进则是3-2-1-4
• 5.在3-2-1情况下，4若是从左进则是4-3-2-1，从右进则是3-2-1-4
• 6.在1-2情况下，3若是从左进则是3-1-2，从右进则是1-2-3
• 7.在3-1-2情况下，4若是从左进则是4-3-1-2，从右进则是3-1-2-4
• 8.在1-2-3情况下，4若是从左进则是4-1-2-3，从右进则是1-2-3-4
• 9.因此各种情况总结为4-3-2-1、3-2-1-4、4-3-2-1、3-2-1-4、4-3-1-2、3-1-2-4、4-1-2-3、1-2-3-4，所以答案为D