第5章〓栈与队列 
本章学习目标

 掌握栈、队列和双端队列的概念

 掌握栈、队列和双端队列的数组描述

 了解栈、队列和双端队列的链式描述

栈(Stack)与队列(Queue)是两种使用频率很高的经典的数据结构，在计算机学科的多个领域(如编译器、操作系统、计算机网络等)得到了广泛的应用。本质上，栈与队列是受限的线性表，由于它们是如此重要，因此栈与队列是独立实现的数据结构。

5.1栈
栈是限制add和remove操作只能发生在表头或表尾的线性表。发生操作的一端叫作栈顶(Top)，另一端叫作栈底(Bottom)。栈就像餐厅的一摞盘子，只能从顶部取用盘子，放回盘子也只能放回顶部。习惯上，add操作叫作压栈(Push)，remove操作叫作出栈(Pop)。

栈具有后进先出(Last In First Out,LIFO)的特点。假设栈已有3个数据A、B、C，栈底在下，栈顶在上，如图5.1(a)所示。执行压栈后D进入栈，D成为栈顶，如图5.1(b)所示。执行出栈后D离开了栈，C成为栈顶，即后压栈的数据先出栈，如图5.1(c)所示。



图5.1压栈和出栈


栈常用于处理这样的问题： 问题一引发了问题二，问题二引发了问题三，解决了问题三后，再返回问题二，继续处理问题二，解决了问题二后再处理问题一。计算机程序的方法调用就使用了栈，调用方法时一般将实参、返回地址、方法返回值等压栈，以保证调用者和被调用者之间交换数据，并且被调用者执行完毕后，能返回调用者。

IStack接口定义了栈： 

public interface IStack<T> {

void clear();

boolean isEmpty();

int size();

T peek();

void push(T x);

T pop();

}

 clear： 删除栈的全部数据，使栈成为空栈。

 isEmpty： 若栈为空栈，则返回真，否则返回假。

 size： 返回栈的数据个数。

 peek： 若栈为空栈，则返回null，否则返回栈顶。

 push： 将数据压栈，作为新的栈顶，若没有空间容纳数据，则抛出异常StackOverflowError。

 pop： 删除并返回栈顶，若栈为空，则抛出异常NoSuchElementException。

5.1.1栈的数组描述

栈的数组描述利用数组元素下标的次序关系表示数据压栈的先后关系，数组的右端为栈顶，如图5.2所示。图5.2(a)是空栈，图5.2(b)的C是栈顶，A是栈底。变量top表示下一个压栈的数据应存入的位置，即栈顶的右邻。



图5.2栈的数组描述


1. CStack类

CStack类是使用数组描述实现的栈。

1public class CStack<T> implements IStack<T>, Iterable<T> {

2private Object［］ elements;

3private int top;

4}

数组elements用于存储栈的数据，字段top等于栈顶右邻的下标，top也是栈的数据个数。

2. 构造器

构造器构造空栈： top=0。

1public CStack(int maxSize) {

2elements = new Object［maxSize］;

3}

代码第2行申请了大小为maxSize的数组用于存放数据。

3. isEmpty方法和size方法

isEmpty方法和size方法使用变量top完成预定的操作。

1public boolean isEmpty() {

2return top == 0;

3}

4public int size() {

5return top;

6}

4. peek方法

peek方法返回栈顶，若栈为空栈，则返回null。

栈顶存储于数组元素elements［top-1］中，代码如下： 

1public T peek() {

2return top == 0 ? null : (T) elements［top - 1］;

3}

5. push方法

push方法将数据压栈。因为peek方法返回null表示空栈，所以压栈的数据不能为null。

1public void push(T x) {

2Objects.requireNonNull(x);

3if (top == elements.length)

4throw new StackOverflowError("full stack");

5elements［top++］ = x;

6}

代码第2行判断数据x是否为null，若为null，则抛出异常NullPointerException。第3行判断栈是否已满，若栈满，则抛出异常。第5行将数据x入栈并作为栈顶，同时更新top，确保top是栈顶右邻的下标。

6. pop方法

pop方法将栈顶出栈并返回栈顶，若栈为空栈，则返回null。

1public T pop() {

2if (top == 0)

3throw new NoSuchElementException();

4@SuppressWarnings("unchecked")

5T result = (T) elements［--top］;

6elements［top］ = null;

7return result;

8}

代码第2行判断是否为空栈，若为空栈，则抛出异常。第5行取出栈顶，并从栈移除栈顶。由于top是栈顶的右邻，top的第一个作用是定位栈顶的位置，第二个作用是移除旧栈顶，明确新栈顶的下标。由于elements［top］仍然引用已出栈的旧栈顶，因此，为了防止内存泄漏，第6行的语句elements［top］=null切断了这个引用。

7. clear方法

clear方法清空栈的数据，清空后，栈的数据个数为0，即top=0。

如果只令top=0，则会造成内存泄漏。如图5.2(b)所示，因为elements［0］、elements［1］、elements［2］仍然引用A、B、C对象，所以垃圾回收器无法收回A、B、C占用的内存空间。

1public void clear() {

2while (top != 0) {

3elements［--top］ = null;

4}

5}

代码第2、3行逐一切断栈与原有数据之间的联系，做到逻辑上清空了栈，物理上也清空了栈。

8. 迭代器

迭代器按照从栈顶到栈底的顺序返回全部数据，代码请参考本书配套资源中的project，不再赘述。

9.  性能分析

使用数组描述实现栈的代码很简单，clear方法的时间复杂度为O(n)，其他方法的时间复杂度为O(1)。所有方法的空间复杂度均为O(1)。

5.1.2栈的链式描述

栈的链式描述使用结点存储数据，利用结点之间的引用关系表示数据压栈的先后关系，这些结点构成了单向链表，如图5.3所示。



图5.3栈的链式描述


1. LinkedStack类

LinkedStack类是使用链式描述实现的栈。字段top引用栈顶结点，字段size记录栈的数据个数，用于保证size方法的时间复杂度为O(1)。空栈的判断条件是size==0或top==null，一般使用后者。

以下是LinkedStack的声明： 

1public class LinkedStack<T> implements IStack<T>, Iterable<T> {

2Node<T> top;

3int size;

4static class Node<T> {

5T data;

6Node<T> next;

7Node(Te, Node<T> p) {

8data = e;

9next = p;

10}

11}

12…

13}

嵌套类Node的字段data存储压栈的数据，字段next引用另一个Node对象，被引用者先于引用者压栈。

2. 构造器

构造器构造空栈： top=null，size=0。

1public LinkedStack() {

2}

LinkedStack类其他方法的代码留作习题。

5.2队列
队列是限制add操作只能发生在表尾， remove操作只能发生在表头的线性表。习惯上，add操作称作入队(Offer)，remove操作称为出队(Poll)。入队的一端叫作队头(Front)，另一端叫作队尾(Rear)。队列就像餐厅购买食物所排的队，后来的人排在队尾，只有队头的人能获得服务，购买食物后离开队。

队列具有先进先出(First In First Out,FIFO)的特点。假设队已有3个数据A、B、C，队头在左，队尾在右，如图5.4(a)所示。执行出队后，队头A出队，如图5.4(b)所示。执行入队后，D成为队尾，如图5.4 (c)所示。



图5.4出队和入队


紧缺资源的分配一般采用先到先得的分配策略，队列常用于解决此类问题。操作系统分配共享打印机时会建立打印机队列，申请者需要排队。网络交换机建立数据包的接收队列和发送队列，汇聚到交换机的数据包需要排队。

IQueue接口定义了队列： 

public interface IQueue<T> {

void clear();

boolean isEmpty();

int size();

T peek(); 

boolean offer(T x);

T poll(); 

}

 clear： 删除队列的全部数据，使之成为空队。

 isEmpty： 若队列为空队，则返回真，否则返回假。

 size： 返回队列的数据个数。

 peek： 若为空队，则返回null，否则返回队头。

 offer： 如果不违反空间限制，则入队。数据成功入队后，返回真，否则返回假。

 poll： 若为空队，则返回null，否则队头出队，返回队头。

5.2.1队列的数组描述

队列的数组描述利用数组元素下标的次序关系表示数据入队的先后关系，数组的左端为队头，右端为队尾，如图5.5所示。变量front表示队头的位置，rear表示下一个入队的数据应存入的位置，即队尾的右邻。出队后，front=front+1，入队后，rear=rear+1。



图5.5队列的数组描述


队列的数组描述面临假溢出问题。图5.5的队经过3次出队，8次入队后，如图5.6(a)所示，rear已经越过数组的右边界，不能再存入数据，似乎已经处于队满状态，但数组的左端尚有空闲的空间可以接纳数据，实际上队列处于未满状态，这就是假溢出现象。

为了解决这个问题，引入了循环队列的概念。循环队列不再是一条直线，而是一个圆，即循环队列是首尾相连的队列。相应的，数组下标也看作是循环的，例如，图5.6(b)的数组的下标为0，1，2，…，10，0，即下标为10的数组元素的右邻是下标为0的数组元素。将图5.6(a)的队列看作循环队列，入队两个数据后的结果如图5.6(b)所示。



图5.6假溢出现象及循环队列


假设数组的长度为m，为了实现数组下标的循环，出队后，front=(front+1) % m，入队后，rear=(rear+1) % m。

将front和rear想象成在运动场的环形跑道上进行3000米比赛的两个运动员，假设rear的实力较强，如果rear追上了front，则发生了套圈现象。调换rear和front的角色，如果发生套圈现象，则是front追上了rear。

队列的数组描述将(rear+1) % m==front作为队满的条件，即如果rear再跑一步就追上了front，图5.6(b)所示的循环队列就处于队满的状态。如果front追上了rear，即front==rear成立，队就处于空队状态。例如，将图5.5视为循环队列，执行3次出队后，front就追上了rear，队列成为空队。

由front和rear可计算出队列的数据个数。front和rear的相对位置有两种情形，第一种情形，front在rear的左边，即rear-front≥0，如图5.5所示，此时，数据个数size为： 

size=rear-front=(rear-front+m) % m

第二种情形，front在rear的右边，即rear-front≤0，如图5.6(b)所示，此时，数据个数size为： 

size=rear+m-front=(rear-front+m) % m

无论哪种情形，都可以使用相同的算式计算数据个数。

1.  CQueue类

CQueue类是使用数组描述实现的队列。

1public class CQueue<T> implements IQueue<T>, Iterable<T> {

2private Object［］ elements;

3private int front;

4private int rear;

5…

6}

数组elements用于存放队列的数据，字段front是存储队头的数组元素的下标，字段rear是存储队尾的数组元素的右邻的下标。

另外，队列的数组描述要维护不变式： 空队时，各数组元素为null。

2.  构造器

构造器构造空栈。

1public CQueue(int maxSize) {

2elements = new Object［maxSize］;

3}

代码第2行创建了长度为maxSize的数组用于存放数据，数组elements的各元素取默认值null。front和rear都取默认值。条件front==rear成立，符合空栈的定义。

3. isEmpty和size方法

isEmpty检测队空的条件front==rear是否成立。size方法根据上面推导的算式计算数据个数。

1public boolean isEmpty() {

2return front == rear;

3}

4public int size() {

5return (rear - front + elements.length) % elements.length;

6}

4. peek方法

peek方法返回队头。若队列为空队，则返回null。

1public T peek() {

2// if (front == rear)

3// return null;

4return (T) elements［front］;

5}

代码第4行返回队头，队头存储于elements［front］。前面介绍的构造器和后面介绍的poll和clear方法共同维护了不变式： 空队时各数组元素为null。空队时，无论front取何值，elements［front］始终为null。因此，可省略第2、3行的语句。

5. offer方法

offer方法向队列增加数据，新增的数据作为队尾。若因为某些原因无法将数据入队，则返回false。

1public boolean offer(T x) {

2if (x == null)

3return false;

4if ((rear + 1) % elements.length == front)

5return false;

6elements［rear］ = x;

7rear = (rear + 1) % elements.length;

8return true;

9}

因为peek方法返回null作为队空的标识，所以null不能作为数据入队。代码第2行检查入队的数据，如果为null，则不能入队，按照约定，第3行返回false。第4行检查队是否已满，如果队满，则数据不能入队，按照约定，第5行返回false。第6行将数据入队，第7行设置rear，使其为队尾的右邻，因数据已经入队，第8行返回true。

6. poll方法

poll方法返回队头，并从队列移除队头。若队列是空队，则返回null。

1public T poll() {

2// if (front == rear)

3// return null;

4T result = (T) elements［front］;

5if (result != null) {

6elements［front］ = null;

7front = (front + 1) % elements.length;

8}

9return result;

10}

代码第4行取出队头，若为null，则表明是空队，第9行返回null。否则，移除这个数据，第6行elements［front］=null，既防止了内存泄漏，又维护了空队时各数组元素为null的不变式，第7行调整front，从队列删除这个数据。

7. clear方法

clear方法清空队的数据，使队列成为空队。

1public void clear() {

2while (front != rear) {

3elements［front］ = null;

4front = (front + 1) % elements.length;

5}

6}

代码第2～5行的while语句将各数组元素置为null，既防止了内存泄漏，又维护了空队时各数组元素为null的不变式。循环结束后，条件front==rear成立，满足了空队的要求。

8. 迭代器

迭代器按照从front到rear的顺序返回队列的全部数据。

1class Itr implements Iterator<T> {

2int cursor;

3Itr() {

4cursor = front;

5}

6public boolean hasNext() {

7if (cursor != rear)

8return true;

9return false;

10}

11@SuppressWarnings("unchecked")

12public T next() {

13T result = (T) elements［cursor］;

14cursor = (cursor + 1) % elements.length;

15return result;

16}

17}

代码第4行，设cursor为front的替身，第14行让cursor追赶rear，第7行判断cursor是否追上了rear，若追上，则已经遍历了队列的全部数据，第9行返回false，否则第8行返回true。

9. 性能分析

使用数组描述实现队列的代码很简单，clear方法的时间复杂度为O(n)，其他方法的时间复杂度为O(1)。所有方法的空间复杂度为O(1)。

5.2.2队列的链式描述

队列的链式描述使用结点存储数据，利用结点之间的引用关系表示数据入队的先后关系，这些结点构成了单向链表。变量front引用队头结点，


图5.7队列的链式描述


变量rear引用队尾结点，如图5.7所示。

1. LinkedQueue类

LinkedQueue类是使用链式描述实现的队列。

1public class LinkedQueue<T> implements IQueue<T>, Iterable<T>, Cloneable {

2Node<T> front;

3Node<T> rear;

4int size;

5static class Node<T> {

6T data;

7Node<T> next;

8Node(Te, Node<T> p) {

9data = e;

10next = p;

11}

12}

13...

14}

字段front引用存储队头的结点，字段rear引用存储队尾的结点，字段size记录队列的数据个数，用于保证方法size()的时间复杂度为O(1)。空队的判断条件是size==0、front==null或rear==null。

嵌套类Node的字段data存储入队的数据，字段next引用另一个Node对象，引用者先于被引用者入队。

2. 构造器

构造器使字段取默认值，构造了空队。

1public LinkedQueue() {

2}

LinkedQueue类的其他方法的代码留作习题。

5.3双端队列
双端队列(Double End Queue，简写为Deque，发音与单词Deck相同)是左、右两端都允许入队和出队的队列，如图5.8所示。



图5.8双端队列


左端入队的数据有先入队和后入队之分，同样，右端入队的数据也有先后之分，但左端入队的数据和右端入队的数据无先后关系。为了统一起见，规定a0为双端队列的第1个数据，a1为第2个数据，an-1为最后一个数据。

双端队列有两种特殊形式。一端允许入队和出队，另一端只允许出队的双端队列叫作入队受限的双端队列。一端允许入队和出队，另一端只允许入队的双端队列叫作出队受限的双端队列。

双端队列兼具栈和队列的功能，但双端队列比栈和队列更灵活。在同一端入队和出队的双端队列就是栈，一端入队，另一端出队的双端队列就是队列。有些问题需要双端队列，请见本章习题的生成滑动窗口最大值数组问题。

IDeque接口定义了双端队列： 

public interface IDeque<T> {

void clear();

boolean isEmpty();

int size();

boolean offerFirst(T x);

T pollFirst(); 

T peekFirst();

boolean offerLast(T x);

T pollLast();

T peekLast();

}

 clear： 清空双端队列的全部数据，使之成为空队。

 isEmpty： 若双端队列为空队，则返回true，否则返回false。

 size： 返回双端队列的数据个数。

 offerFirst： 数据在左端入队。若成功入队，则返回true，否则返回false。

 pollFirst： 左端的数据出队，并返回出队的数据。若双端队列为空队，则返回null。

 peekFirst： 返回左端的数据。若双端队列为空队，则返回null。

 offerLast： 数据在右端入队。若成功入队，则返回true，否则返回false。

 pollLast： 右端的数据出队，并返回出队的数据。若双端队列为空队，则返回null。

 peekLast： 返回右端的数据。若双端队列为空队，则返回null。

5.3.1双端队列的数组描述

双端队列的数组描述利用数组元素下标的次序关系表示数据在队列中的顺序，如图5.9所示。变量left表示左端，right表示右端，数据的顺序是从left到right。左端入队，执行left=left-1后，数据存入数组元素left，左端出队，执行left=left+1。右端入队，数据存入数组元素right，然后执行right=right+1，右端出队，执行right=right-1。



图5.9双端队列的数组描述


双端队列的数组描述与队列的数组描述同样面临假溢出问题，解决方法也是将双端队列视为循环队列，即left=left+1，right=right+1后，如果left、right大于数组的右边界，则令left=0, right=0。left=left-1，right=right-1后，如果left、right小于0，则令left、right 等于数组的右边界。图5.10是图5.9的双端队列在右端入队5个数据后的情形。



图5.10循环双端队列


同队列的数组描述相似，双端队列的数组描述使用left和right计算队列的数据个数。

若双端队列的数据个数等于0，则为空队。若双端队列的数据个数等于数组长度，则为满队列。由于变量left和变量right的设置方式，也可以这样判断空队和满队列： 左端或右端出队时，若left==right成立，则双端队列为空队； 左端或右端入队后，若left==right，则双端队列为满队列。

若双端队列用完了存储空间成为满队列，则立刻扩大存储空间，即双端队列处于满队列是一个临时状态。

1. CDeque类

CDeque类是使用数组描述实现的双端队列。数组elements用于存放队列的数据，字段left记录了左端出队和入队的位置，字段right记录了右端出队和入队的位置。

1public class CDeque<T> implements IDeque<T>, Iterable<T> {

2private Object［］ elements;

3private int left;

4private int right;

5…

6}

双端队列的数组描述维护了不变式： 空队时各数组元素为null。

2. 构造器

构造器构造空队。变量left和变量right等于0，双端队列的数据个数等于0。各数组元素为null，满足了不变式。

1public CDeque(int maxSize) {

2elements = new Object［maxSize］;

3}

3. 辅助方法dec和inc

dec方法用于完成left-1和right-1，若结果小于0，则left、right等于数组的右边界。

1private int dec(int i) {

2if (--i < 0)

3i = elements.length - 1;

4return i;

5}

inc方法用于完成left+1和right+1，若结果超过数组的右边界，则left、right等于0。

1private int inc(int i) {

2if (++i >= elements.length)

3i = 0;

4return i;

5}

4. size方法

若right≥left，size=right-left，如图5.9所示，代码第2行用于计算这种情况的数据个数。若right<left，如图5.10所示，数据分布在两部分，第一部分的数据个数为right，第二部分的数据个数为element.length-left，代码第4行针对这种情况。

1public int size() {

2int i = right - left;

3if (i < 0)

4i += elements.length;

5return i;

6}

5. offerFirst方法

offerFirst方法使数据在左端入队。若成功入队，则返回true，否则返回false。

1public boolean offerFirst(T x) {

2Objects.requireNonNull(x);

3elements［left = dec(left)］ = x;

4if (left == right)

5doubleCapacity();

6return true;

7}

入队的位置是left-1，第3行将数据存入这个位置。第4行测试条件left==right是否成立，若成立，则处于满队列状态，已耗尽了所有存储空间，第5行扩大存储空间，如果无法从系统获得更大的空间，则抛出异常，否则，由于数据已经入队，因此第6行返回true。

6. offerLast方法

offerLast方法使数据在右端入队。若成功入队，则返回true，否则返回false。

right就是入队的位置，入队后要将right设置为新入队数据的右邻，参见图5.9。同样，若用尽了存储空间，则扩大存储空间。

1public boolean offerLast(T x) {

2Objects.requireNonNull(x);

3elements［right］ = x;

4if ((right = inc(right)) == left)

5doubleCapacity();

6return true;

7}

7. pollFirst方法

pollFirst方法使左端的数据出队，并返回出队的数据。若队列为空队，则返回null。

1public T pollFirst() {

2T result = (T) elements［left］;

3if (result != null) {

4elements［left］ = null;

5left = inc(left);

6}

7return result;

8}

代码第2行获取出队的数据，若出队的数据不为null，为了维护不变式，第4行将左端的数据设置为null，第5行更新left，完成出队。第7行，按照接口的约定，返回左端的数据。

8. pollLast方法

pollLast方法使右端的数据出队，并返回出队的数据。若队列为空队，则返回null。代码与pollFirst方法相似。

1public T pollLast() {

2int t;

3T result = (T) elements［t = dec(right)］;

4if (result != null) {

5elements［right = t］ = null;

6}

7return result;

8}

9. peekFirst方法和peekLast方法

peekFirst方法和peekLast方法分别返回双端队列的队头和队尾，若双端队列为空队，则返回null。

1public T peekFirst() {

2return (T) elements［left］;

3}

4public T peekLast() {

5return (T) elements［dec(right)］;

6}

队头和队尾在数组的下标分别是left和right-1，第2行和第5行分别取出队头和队尾并返回。若双端队列是空队，由于构造器、出队、清空等方法维护了不变式，因此返回null。

10. clear方法

数据在数组的存放有两种情形： 一个连续区间，如图5.9所示； 两个连续区间，如图5.10所示。clear方法的一种实现方法是让left追赶right，一边追赶，一边设置数据为null，但是，需要使用%运算。clear方法的另一个实现方法是分别清除两个连续区间，从而避免使用%运算。

1public void clear() {

2for (int i = left, to = (i <= right) ? right : elements.length;; i = 0, to = right) {

3for (; i < to; left++)

4elements［i］ = null;

5if (to == right)

6break;

7}

8left = right = 0;

9}

代码第2行的for语句会循环一次或两次。若初始设置i=left，to=right，即left≤right，如图5.9所示，第3、4行清空这个区间，第6行结束循环。若初始设置i=left，to=elements.length，即left>right，如图5.10所示，则第一次循环，第3、4行清除图5.9右边的区间，第二次循环，i=0，to=right，第3、4行清除图5.9左边的区间。

11. doubleCapacity方法

左端入队或右端入队后，队列可能会处于满队列的状态，条件left==right成立，如图5.11所示。此时，需要调用doubleCapacity方法扩大空间。



图5.11满队列示意图



1private void doubleCapacity() {

2assert left == right;

3int n = elements.length;

4int newCapacity = n << 1;

5if (newCapacity < 0)

6throw new IllegalStateException("Sorry, deque too big");

7Object［］ a = new Object［newCapacity］;

8int p = left;

9int r = n - p;

10System.arraycopy(elements, p, a, 0, r);

11System.arraycopy(elements, 0, a, r, p);

12elements = a;

13left = 0;

14right = n;

15}

代码第4行设置新空间的大小是原空间的2倍。如果原空间很大，再扩大2倍可能超出int类型的表示范围，发生溢出，即newCapacity为负数，则第6行抛出异常。第9行的变量r是从left到数组右边界的数据个数，第10行将原空间的left到数组右边界的数据复制到新空间，占用的位置是0，1，…，r-1，第11行将原空间从0到left-1的数据复制到新空间，占用的位置是r，r+1，…，r+p-1。队列在新空间的第一个数据的位置是0，最后一个数据的位置是n-1。

12. 性能分析

基于数组描述的双端队列的代码很简单，clear方法和doubleCapacity方法的时间复杂度为O(n)，其他方法的时间复杂度为O(1)。所有方法的空间复杂度为O(1)。

5.3.2双端队列的链式描述

双端队列的链式描述利用结点之间的引用关系表示数据在队列中的顺序，这些结点构成了单向链表，变量left引用队头结点，变量right引用队尾结点，如图5.12所示。



图5.12双端队列的链式描述


双端队列的链式描述留作练习。

小结
栈和队列是经典的数据结构，用途广泛。双端队列兼具栈和队列的功能，并且更加灵活。

Java类库无Stack接口，但有Queue接口和Deque接口，Deque接口扩展了Queue接口。Deque接口包含栈的push、pop操作，这两个操作发生在双端队列的左端，等同于offerFirst和pollFirst。Stack类是栈的一个早期实现，已经过时。ArrayDeque类和LinkedList类实现了Deque接口，前者基于数组描述，后者基于链式描述。

习题
1. 选择题

(1) 一个队列的入队序列是1，2，3，4,则出队序列是()。

A.  4，3，2，1B. 1，2，3，4

C. 1，4，3，2D. 3，2，4，1

(2) 队列的操作有()。

A. 对队列中的数据排序

B. 取出最近入队的数据

C. 在队列的数据之间插入新的数据

D. 删除队头的数据

(3) 为了解决计算机与打印机之间的速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据一次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。

A. 栈B. 队列C. 树D. 图

(4) 如果队列允许在其两端进行入队，但仅允许在一端进行出队。若数据元素a，b，c，d，e依次入队后再出队，则不可能得到的出队序列是()。

A.  b，a，c，d，eB. d，b，a，c，e

C. d，b，c，a，eD. e，c，b，a，d

(5) 最适合用作链式描述的队列的链表是()。

A. 带队头指针和队尾指针的循环单向链表

B. 带队头指针和队尾指针的非循环单向链表

C. 只带队头指针的非循环单向链表

D. 只带队头指针的循环单向链表

(6) 最不适合用作链式描述的队列的链表是()。

A. 只带队头指针的非循环双链表B. 只带队头指针的循环双链表

C. 只带队尾指针的循环双链表D. 只带队尾指针的循环单向链表

(7) 若用数组A［6］实现循环队列，且当前rear和front分别为1和5，当从队列中删除一个数据元素，再加入两个数据元素时，rear和front分别为()。

A. 3和4B. 3和0C. 5和0D. 5和1

(8) 最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件为()。

A. (rear+1) % n==frontB. rear==front

C. rear+1==frontD. (rear-1) % n==front

(9) 现有队列Q和栈S，初始时Q中的数据依次为1，2，3，4，5，6(1在队头)，S为空。若仅允许下列3种操作： 出队并输出队头； 出队并将队头压栈； 出栈并输出栈顶，则不能得到的输出序列是()。

A.  1，2，5，6，4，3B. 2，3，4，5，6，1

C. 3，4，5，6，1，2D. 6，5，4，3，2，1

(10) 设栈S和队列Q的初始状态为空，数据e1，e2，e3，e4，e5，e6依次通过栈S，一个数据出栈后即进队列Q，若6个数据出队的序列为e2，e4，e3，e6，e5，e1，则栈的容量至少为()。

A.  6B. 4C. 3D. 2

2. 填空题

(1) 队列是一种受限的线性表，允许插入的一端称为，允许删除的一端称为，对队列的访问是按照的原则进行的。

(2) 使用链式描述实现队列时，需要两个引用变量分别引用和。

(3) 在具有n个数据的非空队列插入或删除一个数据的时间复杂度为。

(4) 引入循环队列是为了克服。

(5) 区分循环队列的满与空，有、和方法。

3. 应用题

(1) 实现链式描述的栈LinkStack，需要实现IStack接口。

(2) 实现链式描述的队列LinkQueue，需要实现IQueue接口。

(3) 为类LinkQueue增加方法LinkQueue split()，将奇数位置的数据保留在原队列，偶数位置的数据放到新队列返回。

(4) 为类CQueue增加方法 T［］ toArray()，按照队头到队尾的次序将队列中的数据存放到数组T［］，即队头放在T［0］，以此类推，队尾放在T［n-1］，n是队列中的数据的个数。

(5) 先执行1×106次offer操作，然后执行1×106次poll操作。测试链式描述队列和数组描述实现的队列的性能。

(6) 实现链式描述的双端队列LinkedDeque，需要实现IDeque接口。

(7) 生成滑动窗口最大值数组问题。有一个整型数组和一个大小为w的窗口从数组的最左边滑动到最右边，窗口每次向右滑动一个位置，编写代码输出各窗口的最大值。

例如，数组为5，4，6，5，3，1，6，2，窗口大小为3，用符号［］表示窗口，则各窗口的数据及最大值如下： 

［5，4，6］，5，3，1，6，2

5，［4，6，5］，3，1，6，2

5，4，［6，5，3］，1，6，2

5，4，6，［5，3，1］，6，2

5，4，6，5，［3，1，6］，2

5，4，6，5，3，［1，6，2］

输出结果为6，6，6，5，6，6。提示，使用输入受限的双端队列。

(8) 编写一个类，用两个栈实现队列，需要实现IQueue接口。