-
这一类问题要考察的核心其实是元素进出栈、队列的规则。
-
拿栈来说,元素进出的顺序是相反的,后进先出,即LIFO。运用这个特性,我们可以把一个栈的全部元素逆序移至另一个栈。
举例来说,有一组元素排成序列abcd,保存在栈X中,其中d为栈顶元素,a为栈底元素。另外还有一个栈Y,是空的。当我们把序列中的元素逐个从栈X弹出,压入栈Y,将产生新序列dcba,这恰恰是原序列abcd的逆序。其实,每经过一次调换,都可以让原序列的栈底元素变成新序列的栈顶。
利用这个规律,通过一个序列在两个栈之间来回的切换,我们可以像操作栈顶元素一样的操作栈底元素。一个两端都可操作的序列不就已经满足队列的要求了吗,甚至可以做成双端队列。
-
一个序列在两个栈之间调换的具体过程:
栈X a b c d 栈Y 栈X a b c 栈Y d
栈X | a b |
---|---|
栈Y | d c |
栈X | a |
---|---|
栈Y | d c b |
栈X|
---|---
栈Y|d c b a
-
再来看队列,将序列从队列X调换到队列Y以后,序列的顺序保持不变。而在调换的过程中,根据不同的需求,我们可以灵活地选择把序列当中的某一段调换过去,某一段舍弃掉。被舍弃的那一段相当于是被移除了序列。例如,我们可以舍弃最后进入队列的队尾元素。这样一来进出的规则变成了LIFO,而这恰好是一个栈。
-
一个序列在两个队列之间调换,实现出栈
队列X a b c d 队列Y 队列X b c d 队列Y a
队列X | c d |
---|---|
队列Y | a b |
队列X | d |
---|---|
队列Y | a b c |
- 至此,d元素出栈。