015--数据结构之队列的使用+面试题

VIP免费

2024-12-11 3 0 76.29KB 11 页 5.9玖币

侵权投诉

数据结构之队列的使用 + 面试题

队列（Queue ）：与栈相对的一种数据结构，集合（Collection）的一个子类。队列允许

在一端进行插入操作，而在另一端进行删除操作的线性表，栈的特点是后进先出，而队列

的特点是先进先出。队列的用处很大，比如实现消息队列。

Queue 类关系图，如下图所示：

enter image description here

注：为了让读者更直观地理解，上图为精简版的 Queue 类关系图。本文如无特殊说明，

内容都是基于 Java 1.8 版本。

队列（Queue）

1）Queue 分类

从上图可以看出 Queue 大体可分为以下三类。

•双端队列：双端队列（Deque ）是 Queue 的子类也是 Queue 的补充类，头部和尾部

都支持元素插入和获取。

•阻塞队列：阻塞队列指的是在元素操作时（添加或删除），如果没有成功，会阻塞等

待执行。例如，当添加元素时，如果队列元素已满，队列会阻塞等待直到有空位时再

插入。

•非阻塞队列：非阻塞队列和阻塞队列相反，会直接返回操作的结果，而非阻塞等待。

双端队列也属于非阻塞队列。

2）Queue 方法说明

Queue 常用方法，如下图所示：

enter image description here

方法说明：

• add(E) ：添加元素到队列尾部，成功返回 true，队列超出时抛出异常；

• offer(E) ：添加元素到队列尾部，成功返回 true ，队列超出时返回 false；

• remove() ：删除元素，成功返回 true ，失败返回 false；

• poll() ：获取并移除此队列的第一个元素，若队列为空，则返回 null；

• peek() ：获取但不移除此队列的第一个元素，若队列为空，则返回 null；

• element()：获取但不移除此队列的第一个元素，若队列为空，则抛异常。

3）Queue 使用实例

Queue<String> linkedList = new LinkedList<>();

linkedList.add("Dog");

linkedList.add("Camel");

linkedList.add("Cat");

while (!linkedList.isEmpty()) {

System.out.println(linkedList.poll());

}

程序执行结果：

Dog

Camel

Cat

阻塞队列

1）BlockingQueue

BlockingQueue 在java.util.concurrent 包下，其他阻塞类都实现自 BlockingQueue 接

口，BlockingQueue 提供了线程安全的队列访问方式，当向队列中插入数据时，如果队列

已满，线程则会阻塞等待队列中元素被取出后再插入；当从队列中取数据时，如果队列为

空，则线程会阻塞等待队列中有新元素再获取。

BlockingQueue 核心方法

插入方法：

• add(E) ：添加元素到队列尾部，成功返回 true，队列超出时抛出异常；

• offer(E) ：添加元素到队列尾部，成功返回 true ，队列超出时返回 false ；

• put(E) ：将元素插入到队列的尾部，如果该队列已满，则一直阻塞。删除方法：

• remove(Object) ：移除指定元素，成功返回 true ，失败返回 false；

• poll() ：获取并移除队列的第一个元素，如果队列为空，则返回 null；

• take() ：获取并移除队列第一个元素，如果没有元素则一直阻塞。检查方法：

• peek() ：获取但不移除队列的第一个元素，若队列为空，则返回 null。

2）LinkedBlockingQueue

LinkedBlockingQueue 是一个由链表实现的有界阻塞队列，容量默认值为

Integer.MAX_VALUE，也可以自定义容量，建议指定容量大小，默认大小在添加速度大于

删除速度情况下有造成内存溢出的风险，LinkedBlockingQueue 是先进先出的方式存储元

素。

3）ArrayBlockingQueue

ArrayBlockingQueue 是一个有边界的阻塞队列，它的内部实现是一个数组。它的容量是

有限的，我们必须在其初始化的时候指定它的容量大小，容量大小一旦指定就不可改变。

ArrayBlockingQueue 也是先进先出的方式存储数据，ArrayBlockingQueue 内部的阻塞队

列是通过重入锁 ReenterLock 和Condition 条件队列实现的，因此 ArrayBlockingQueue 中

的元素存在公平访问与非公平访问的区别，对于公平访问队列，被阻塞的线程可以按照阻

塞的先后顺序访问队列，即先阻塞的线程先访问队列。而非公平队列，当队列可用时，阻

塞的线程将进入争夺访问资源的竞争中，也就是说谁先抢到谁就执行，没有固定的先后顺

序。

示例代码如下：

// 默认非公平阻塞队列

ArrayBlockingQueue queue = new ArrayBlockingQueue(6);

// 公平阻塞队列

ArrayBlockingQueue queue2 = new ArrayBlockingQueue(6,true);

// ArrayBlockingQueue 源码展示

public ArrayBlockingQueue(int capacity) {

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

数据结构之队列的使用+面试题队列（Queue）：与栈相对的一种数据结构，集合（Collection）的一个子类。队列允许在一端进行插入操作，而在另一端进行删除操作的线性表，栈的特点是后进先出，而队列的特点是先进先出。队列的用处很大，比如实现消息队列。Queue类关系图，如下图所示：enterimagedescriptionhere注：为了让读者更直观地理解，上图为精简版的Queue类关系图。本文如无特殊说明，内容都是基于Java1.8版本。队列（Queue）1）Queue分类从上图可以看出Queue大体可分为以下三类。•双端队列：双端队列（Deque）是Queue的子类也是Queue的补充类，...

展开>> 收起<<

015--数据结构之队列的使用+面试题.docx

共11页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

015--数据结构之队列的使用+面试题

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: