介绍
队列，queue是一种 先进先出(First In First Out，缩写 FIFO )的数据结构
从 队尾添加 元素，从 队头删除 元素
最先插入 在元素将是 最先被删除；最后插入的 元素将 最后被删除，因此队列称为“先进先出”（FIFO—first in first out）
一般不支持随机访问，即不能任意访问中间的元素
概念
队尾(Rear)：允许插入元素的一端称
队头（Front)：允许删除元素的一端称
例子
下面设顺序队列 Q 的容量为 6，其队头指针为 front，队尾指针为 rear，头、尾指针和队列中元素之间的关系如图：
循环队列
顺序队列的 缺点
在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针，如下图
由于顺序队列的存储空间 容量是提前设定的，所以队尾指针会有一个 上限值，当队尾指针达到该上限时，就 不能只通过修改队尾指针 来实现新元素的 入队 操作了，如上图
循环队列
若将顺序队列假想成一个 环状结构（通过整除取余运算实现)，则可维持入队、出队操作运算的简单性，如图：
优点
入队和出队操作都不需要移动队列中的其他元素
缺点
当出队操作导致 队列变为空 时，则有 Q.rear==Q.front，如图 d所示
若入队操作导致 队列满，则 Q.rear==Q.front，如图e所示。
也就是说：在队列空和队列满的情况下，仅根据 Q.rear==Q.front ， 无法断 定队列的状态。
解决
下两种处理方式：
方法1：设置一个标志，以区别头、尾指针的值相同时队列是空还是满；
方法2：牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满，如图f所示，而头、尾指针的值相同时表示队列为空。
概念
队空条件：Q.head = Q.rear，头尾指针指向同一个位置，如图a
队满条件：(Q.rear + 1)%size = Q.head
队列长度：(Q.rear - Q.head + size) % size。提示： ( Q.rear - head 可能为负数，所以 + size )
题
对于一个长度为n(n>1)且元素互异的序列，令其所有元素依次通过一个 初始为空的 栈 后，再通过一个 初始为空的 队列。假设队列和栈的容量都足够大，且只要栈非空就可以进行出栈操作，只要队列非空就可以进行出队操作，那么以下叙述中，正确的是（）
A、出队序列和出栈序列一定互为逆序
B、出队序列和出栈序列一定相同
C、入栈序列与入队序列一定相同
D、入栈序列与入队序列一定互为逆序
分析
执行顺序如下：
入栈 -> 出栈 -> 入队 -> 出队
关键：只要栈非空就可以进行出栈操作，有一个元素入栈就可以出栈，也可能有两个元素入栈，然后出栈
比如：序列是：1,2,3
执行过程如下：
1入栈
2入栈
2出栈，2入队，2出队
3入栈
3出栈，3入队，3出队
1出栈，1入队，1出队
规律：
- 入栈与出栈不相同
- 出栈后，又入队，所以 出栈 等于 入队
- 队列是 先进先出，所以入队 等于 出队
总结：
- 入栈 不等于 出栈
- 出栈 等于 入队 等于 出队
所以：A 错，B对，C错，D错（不一定）
答案
B
题
设有 栈S 和 队列Q 初始状态为空，数据元素序列 a,b,c,d,e,f 依次通过栈S，且多个元素从S出栈后立即进入队列Q，若出队的序列是 b,d,f,e,c,a ,则s中的元素最多时，栈底到栈顶的元素依次为（）。
A、 a,b,c
B、a,c,d
C、a,c,e,f
D、a,d,f,e
分析
执行顺序如下：
入栈 -> 出栈 -> 入队 -> 出队
入栈 后 出栈 // 上面可知，入栈与出栈不相等
出栈 后 入队 // 出栈的结果，又入队，所以 出栈 等于 入队
入队 后 出队 // 先进先出，所以入队 等于 出队
总结：
入栈 不等于 出栈
出栈 等于 入队 等于 出队
所以 b,d,f,e,c,a 也就是出栈的结果
则s中的元素最多时，栈底到栈顶的元素，如下图：
答案
C
题
双端队列 是指在队列的 两个端口 都可以 加入 和 删除 元素，如下图所示。现在要求元素 进队列 和 出队列 必须在 同一端口，即从A端进队的元素必须从A端出、从B端进队的元素必须从B端出，则对于4个元素的序列 a、b、c、d，若要求前2个元素 (a、b) 从A端口按次序全部进入队列，后两个元素 (c、d) 从B端口按次序全部进入队列，则不可能得到的出队序列是（）
A、d、a、b、c
B、d、c、b、a
C、b、a、d、c
D、b、d、C、a
分析
将 (a、b) 依次进入左侧端口， (c、d) 依次进入右侧端口，如下图：
关键： 此时类似栈的操作：先进后出，因为同一个端口进出
总结顺序：
- b先出，a后出
- d先出，c后厨
- bd谁先出不确定
- ac谁先出不确定
A、d、a、b、c a比b先出，不可能
B、d、c、b、a 可能
C、b、a、d、c 可能
D、b、d、C、a 可能
答案
A
题
设某循环队列Q的定义中有front和rear两个域变量，其中，front指示队头元素的位置，rear指示队尾元素之后的位置，如下图所示。若该队列的容量为M，则其长度为（ ）
A、(Q.rear-Q.front +1)
B、(Q.rear-Q.front+M)
C、(Q.rear-Q.front+1)%M
D、(Q.rear-Q.front+M)%M
答
D