mirror of
https://github.com/Didnelpsun/CS408.git
synced 2026-02-04 11:24:10 +08:00
50 lines
3.5 KiB
Markdown
50 lines
3.5 KiB
Markdown
# 队列习题
|
||
|
||
## 顺序队列
|
||
|
||
**例题** 火车车轨入口到出口之间有$n$条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道且每条道路可以容纳任意多数量的列车。现有编号为$1\sim9$的$9$列列车，驶入的次序依次是$8,4,2,5,3,9,1,6,7$。若期望驶出的次序依次为$1\sim9$，则$n$至少是()。
|
||
|
||
解：这个题目是一个多队列问题。根据题意：入队顺序为$8,4,2,5,3,9,1,6,7$，出队顺序为$1\sim9$。入口和出口之间有多个队列（$n$条轨道)，且每个队列（轨道）可容纳多个元素（多列列车），为便于区分，队列用字母编号。分析如下：显然先入队的元素必须小于后入队的元素（否则，若$8$和$4$入同一队列，$8$在$4$前面，则出队时也只能$8$在$4$前面），这样$8$入队列$A$，$4$入队列$B$，$2$入队列$C$，$5$入队列$B$（按照前述原则“大的元素在小的元素后面”也可将$5$入队列$C$，但这时剩下的元素$3$就必须放入一个新的队列中，无法确保“至少”，所以要最接近的一个队列），$3$入队列$C$，$9$入队列$A$，这时共占了$3$个队列，后面还有元素$1$，直接再用一个新的队列$D$，$1$从队列$D$出队后，剩下的元素$6$和$7$或入队列$B$，或入队列$C$。综上，共占用了$4$个队列。
|
||
|
||
## 循环队列
|
||
|
||
**例题** 已知循环队列存储在一维数组$A [0\cdots n-1]$中，且队列非空时$front$和$rear$分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在$A[0]$处，则初始时$front$和$rear$的值分别是()。
|
||
|
||
$A.0$，$0$
|
||
|
||
$B.0$，$n-1$
|
||
|
||
$C.n-1$，$0$
|
||
|
||
$D.n-1$，$n-1$
|
||
|
||
解：$B$。根据题意，第一个元素进入队列后存储在$A[0]$处，此时$front$和$rear$值都为$0$。入队时由于要执行$(rear+1)\%n$操作，所以若入队后指针指向$0$，则$rear$初值为$n-1$，而由于第一个元素在$A[0]$中，插入操作只改变$rear$指针，所以$front$为$0$不变。
|
||
|
||
## 双端队列
|
||
|
||
一般双端队列都是给出一个输入序列，然后给定一个受限的队列，判断给出的输出序列是否可以得到。
|
||
|
||
假设输入序列为$I_1,I_2,\cdots,I_n$。输出序列为$O_1,O_2,\cdots,O_n$。
|
||
|
||
### 输出受限队列
|
||
|
||
这是经常考到的，方法也比较简单。
|
||
|
||
由于只能一端输出，所以是输入决定输出，怎么样输入，队列中的序列是什么样，输出就是什么样，所以可以不用关心输出的问题，而是关心给定序列如何通过左右两边输入。
|
||
|
||
假定只在左侧可以输出，右侧不可以输出，两端都可以输入。
|
||
|
||
首先确定输入序列的第$i$个字符$I_i$在输出序列$O$中的位置$p_i$，然后第$i+1$个字符$I_{i+1}$必然是$p_{i+1}$或$p_{i-1}$两个位置，否则无法得到。
|
||
|
||
已知输入序列为$1,2,3,4,5$，输出序列为$4,3,1,2,5$。
|
||
|
||
输入字符|输出位置|输入方向|当前序列
|
||
:------:|:------:|:------:|:------:
|
||
1|3|→|1
|
||
2|4|←|12
|
||
3|2|→|312
|
||
4|1|→|4312
|
||
5|5|←|43125
|
||
|
||
从这个例子可以看出，对于输入序列而言，最早输入的肯定被晚输入的字符夹住，如果是递增的数字的话，小的数字必然在输出序列中间，两边的数字大于中间的数字，整体从小到大向外放射。如果出现了小大小的情况，如$3,1,5,2$，那这绝对是错误的，因为$5$是后来输入的，只会放在外侧，不可能被先输入的小数字$1,2$夹住。
|