1. 队列¶
1.1. 学习目标¶
完成本模块后，学生将能够：
说出基本 Java 数据结构的功能和用途
说明 Java 中队列（Queues）的关键特征
在 Java 中构建并填充队列（Queues）
1.1.1. 建议阅读¶
第 10 章： 队列、双端队列和优先队列（Queues, Deques, and Priority Queues） 以及 第 11 章：队列、双端队列和优先队列的实现（Queue, Deque, and Priority Queue Implementations） ，选自 Frank M. Carrano 和 Timothy Henry 所著 Data Structures and Abstractions with Java
1.2. 交互式：队列简介¶
跟着做、练习与探索
- 下载视频中的 java 文件（见下面）并在 Eclipse 中自行运行和探索。你可以下载本例的独立 *.java 文件。要运行独立的 *.java 文件，你需要
创建一个新的 Eclipse 项目，然后
在项目内创建一个名为"example"的包（类顶部的包名必须与文件在 Eclipse 项目中放置位置的包名一致），最后
下载并将独立的 *.java 文件导入到所创建的包中。
QueueInterface.java
(right click-> save link as...)package queue;
/**
An interface for the ADT queue.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public interface QueueInterface
{
/** Adds a new entry to the back of this queue.
@param newEntry An object to be added. */
public void enqueue(T newEntry);
/** Removes and returns the entry at the front of this queue.
@return The object at the front of the queue.
@throws EmptyQueueException if the queue is empty before the operation. */
public T dequeue();
/** Retrieves the entry at the front of this queue.
@return The object at the front of the queue.
@throws EmptyQueueException if the queue is empty. */
public T getFront();
/** Detects whether this queue is empty.
@return True if the queue is empty, or false otherwise. */
public boolean isEmpty();
/** Removes all entries from this queue. */
public void clear();
} // end QueueInterface
Video Slides: QueueIntro.pdf
1.3. 检查点 1¶
1.4. 编程实践：队列 1¶
1.5. 交互式：链式队列简介与入队¶
跟着做、练习与探索
LinkedQueuesEnqueue.pdf
1.6. 检查点 2¶
1.7. 交互式：链式队列的移除与更多操作（出队和其他方法）¶
跟着做、练习与探索
LinkedQueueRemove.pdf
1.8. 检查点 3¶
1.9. 交互式：双端队列简介¶
跟着做、练习与探索
- 下载视频中的 java 文件（见下面）并在 Eclipse 中自行运行和探索。你可以下载本例的独立 *.java 文件。要运行独立的 *.java 文件，你需要
创建一个新的 Eclipse 项目，然后
在项目内创建一个名为"example"的包（类顶部的包名必须与文件在 Eclipse 项目中放置位置的包名一致），最后
下载并将独立的 *.java 文件导入到所创建的包中。
DequeInterface.java
(right click-> save link as...)
DequeIntro.pdf
package deque;
/**
* An interface for the ADT dequeue.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
* @param generic type for the deque
*/
public interface DequeInterface
{
/**
* Adds a new entry to the front of this dequeue.
*
* @param newEntry
* An object to be added.
*/
public void addToFront(T newEntry);
/**
* Adds a new entry to the back of this dequeue.
*
* @param newEntry
* An object to be added.
*/
public void addToBack(T newEntry);
/**
* Removes and returns the front entry of this dequeue.
*
* @return The object at the front of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T removeFront();
/**
* Removes and returns the back entry of this dequeue.
*
* @return The object at the back of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T removeBack();
/**
* Retrieves the front entry of this dequeue.
*
* @return The object at the front of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T getFront();
/**
* Retrieves the back entry of this dequeue.
*
* @return The object at the back of the dequeue.
* @throws EmptyDequeException
* if the dequeue is empty before the operation.
*/
public T getBack();
/**
* Detects whether this dequeue is empty.
*
* @return True if the queue is empty, or false otherwise.
*/
public boolean isEmpty();
/**
* Removes all entries from this dequeue.
*/
public void clear();
} // end DequeInterface
1.10. 检查点 4¶
1.11. 交互式：双端队列的移除与小结¶
跟着做、练习与探索
Video Slides DequeRemoveAndWrapUp.pdf
1.12. 检查点 5¶
1.13. 交互式：ArrayQueue——队列的数组实现¶
1.14. 检查点 6¶
1.15. 交互式：ArrayQueue——一个未使用的位置¶
1.16. 检查点 7¶
1.17. 交互式：ArrayQueue——确保容量¶
1.18. 检查点 8¶
1.19. 交互式：ArrayQueue 小结¶
空队列异常
package queue;
/**
* A class of runtime exceptions thrown by methods to indicate that a queue is
* empty.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class EmptyQueueException extends RuntimeException {
/**
* serial Version UID
*/
private static final long serialVersionUID = 960025440830878197L;
public EmptyQueueException() {
this(null);
} // end default constructor
public EmptyQueueException(String message) {
super(message);
} // end constructor
} // end EmptyQueueException
