【数据结构】入队序列出队序列问题（以21年408真题举例）

题型说明

• 一般是一个队列，其中一边可以入队，另一边可以入队和出队
• 只可入队的含义是从这个方向是以队列形式存在
• 可以入队和出队表示此边以堆形式存在

怎么分析？

以21年408真题举例

考点分析

• 出队序列存在两种情况：入之后就出；等所有元素入完再出

• 两种情况区别：

  • 第一种需要思考入队方向和出队时机，较难分析，但是也不会让你分析太多
  • 第二种仅需考虑入队方向

• 先分析一边入队一边出队的，然后会剩余一部分序列，是最后出队的 （参考下面例题）

分析步骤

• 找到因为出队元素大而保存在队列中的子序列

这里的出队元素大是什么意思？我举例说明一下：
假如有出队序列 5, 4, 3, 2, 1 。那么，5是最早出队的，此时序列中还存在 4, 3, 2, 1 ，这个序列就是因为出队元素大而保存的子序列
拿选项A举例：5,4,3,1,2 其中5先出，但是5是最后一个入队的，说明此时队列中积压了4,3,1,2这个序列。 这个序列是在入队的时候是不存在一边入一边出的问题的，可以仅思考入队方向了。

• 对于选项A、B，5是最后入的但是却最先出，分析一下：

  • 首先，此时队列中海存放着4个元素
  • 5只可能是从堆的那一头入然后直接出的（这里只需要找到一个合理的解释就行）
  • 队列中4个元素的序列不存在入的时候直接出的问题

• A：对4,3,1,2进行分析

  • 此时分许方法较简单，不需考虑出队时机，只需考虑入队方向即可
  • 此时队列中数据的排布应该是：2,1,3,4
  • 入队的序列为1,2,3,4
  • 此时1从左入，2左入，3右入，4右入，刚好可以凑成这个序列，故A正确，B同理 （其实这个过程看一下就出来了，菜就要多练（狗头））

• 对于选项C、D

  • 观察，5最后入却最晚出，说明此时5是从左入，且入的时候其余四个元素都在序列中，不需考虑出的时机

• D：对4,1,3,2进行分析

  • 1左入，2右入，3不太行
  • 1右入，2不太行
  • D不太行

• C：对2,1,3进行分析

  • 队列中为3,1,2,4
  • 1右入，2右入，3左入，4右入 其实这一步也一眼就能看出来，菜就多练（狗头）

答案选：D