我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java 集合框架 Queue 和 Stack 体系

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java 集合框架 Queue 和 Stack 体系

Stack

栈结构类型,表示对象的后进先出堆栈。Stack继承自Vector,并拓展了五个允许将容器视为栈结构的操作。

包括常见的poppush操作、以及查看栈顶元素的方法、检查栈是否为空的方法以及从栈顶向下进行搜索某个元素,并获取该元素在栈内深度的方法。

Deque 接口及其实现提供了一组更完整的 LIFO 堆栈操作能力,应该优先考虑使用 Deque 及其实现。例如:

Deque<Integer> stack = new ArrayDeque<Integer>();

Queue

Queue接口定义了队列的能力,它继承自Collection ,除了基本的集合操作外,队列提供了额外的插入、获取、检查等操作。

public interface Queue<E> extends Collection<E> {
    // 在不违反容量限制的情况下立即将指定元素插入此队列,成功时返回 true,如果当前没有可用空间则抛出 IllegalStateException。
    boolean add(E e);
    // 在不违反容量限制的情况下立即将指定元素插入此队列。 在使用容量受限的队列中,一般最好使用这种方法添加,仅通过抛出异常可能无法插入元素。
    boolean offer(E e);
    // 检索并删除此队列的头部。 此方法与 poll 的不同之处仅在于如果此队列为空,它将引发异常。
    E remove();
    // 检索并移除此队列的头部,如果此队列为空,则返回 null。
    E poll();
    // 检索但不删除此队列的头部。 此方法与 peek 的不同之处仅在于如果此队列为空,它将引发异常。
    E element();
    // 检索但不删除此队列的头部,如果此队列为空,则返回 null。
    E peek();
}

可以看出,每一种操作都存在两种定义,一种是在操作失败的情况下强制抛出异常的,另一种则是返回null不强制抛出异常的。

 Throws exceptionReturns special value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

队列通常是先进先出的,所以对元素的排序方式也是以先进先出的顺序的,但是有特殊情况,例如,优先级队列是根据比较元素的优先级进行排序的;另一种例子是后进先出队列,即栈结构。

无论使用哪种排序,队列的头部元素都是通过调用removepoll删除的。在 FIFO 队列中,所有的新元素都是插入到队列的尾部的,其他类型的队列可能使用不同的插入规则,每个Queue的实现都必须明确指定其排序方式。

队列的另一个特性是不允许插入null ,尽管在某些实现中,例如LinkedList,允许存储null。但在这种实现中,也不应该将null插入到队列中,因为 null 被 poll 方法作为特殊返回值,以表明队列不包含任何元素。

队列的实现通常不定义hashCodeequals,因为对于具有相同的元素,但具有不同的排序方式的队列,基于元素的相等并不是很好的定义方式。

Deque

Deque继承自 Queue,是一种支持两端元素插入和移除的顺序结构集合,简称 “双端队列” 。大多数双端队列对容量没有固定限制。

Deque接口主要拓展了对于双端队列两端元素操作的方法,也是两种形式,一种抛出异常,一种返回特殊值 null 的形式。

Deque可以当作 FIFO 队列使用,所以它的一些拓展的方法等效于Queue的一些方法:

Deque作为 LIFO 队列使用时(栈结构),它也会有一些等价于Stack的方法:

其他特性

List接口不同,此接口不支持对元素的索引访问。

另外虽然没有严格要求Deque的实现禁止插入null元素,但在使用中的确应该尽量避免插入null,因为null元素被各种操作方法作为特殊的返回值,这里和 Queue 一样。

另一个与Queue相同的是,它也没有定义需要实现hashequals方法,理由和Queue是一样的。

BlockingQueue

BlockingQueueQueue接口的另一个重要子接口,它用来代表一个可阻塞的队列。支持在检索元素是,等待队列变为非空再返回数据。

BlockingQueue有四种类型,用来解决当前不能立刻处理,需要再未来某个时间点下满足指定条件才执行的操作。

  • 抛出异常
  • 返回特殊值
  • 无限期阻塞当前线程,直到操作成功
  • 在有限时间内阻塞当前线程,超时即放弃执行

以下这张表是同一个行为在不同类型的方法表:

特点

  • 不支持空元素:BlockingQueue不接受空元素。在尝试添加、放置或提供null时,实现会抛出NullPointerException。 null用作标记值以指示轮询操作失败。
  • 容量受限:可能是容量受限的,在给定时间内,可能只有一个剩余容量,超出该容量就不能在不阻塞的情况下放置其他元素。
  • 主要用于实现生产者-消费者队列,但还支持Collection接口。
  • 线程安全需要它的实现类自身去实现。
  • 批量操作不能保证原子性。
  • 内存一致性:和其他并发集合一样,在一个线程中实现将一个对象存入BlockingQueue的操作,会发生在下一个其他线程对BlockingQueue中的该元素读取或移除之前。

PriorityQueue 优先级队列

PriorityQueue是一个基于优先级堆的无界限优先级队列。它是 Queue的直接实现类,优先级队列的元素排序有两种情况:

  • 根据元素的自然存储顺序
  • 队列构造时提供的Comparator进行比较后排序

排序方式取决于具体的构造函数的参数Comparator

    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

特点

优先级队列不允许null元素,依赖于自然排序的优先级队列也不允许插入不可比较的对象,否则会导致ClassCastException

底层实现是通过数组来保存数据的:

transient Object[] queue;

不是线程安全的。

扩容机制

优先级队列的容量是没有限制的,但是内部存储元素的结构实际上是一个数组,它的扩容机制是有规律的。

初始化默认容量 11 ,后续扩容总是扩容到与队列元素数量相同大小,这一点和ArrayList基本一致。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException(); // 不允许 null 元素
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1); // 真正的扩容方法
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50% 默认扩容量
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
  • 如果旧的队列容量 < 64 ,每次扩容 100% 并加 2 。超过 64,每次扩容旧容量的 50 %。
  • 如果新容量超出最大数组容量。则通过hugeCapacity()计算容量:
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  • 如果需要的容量超过数组最大容量,则限制队列容量为 Int 的最大值。
  • 如果需要的容量没超过数组最大容量,则限制队列容量为数组最大容量MAX_ARRAY_SIZE

ArrayDeque

数组双端队列,是一种可调整大小的数组实现,没有容量限制。它会根据需要自动扩容。

继承关系

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
  • AbstractCollection:提供了一些集合接口能力的基本封装。
  • 双端队列
  • 可通过Object.clone()方法快速复制
  • 支持序列化

底层实现

底层数据结构是一个数组:

transient Object[] elements;
transient int head;
transient int tail;

通过headtail作为索引来支持双端队列的特性。

扩容机制

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException(); // 不允许 null 
        elements[head = (head - 1) & (elements.length - 1)] = e; // 防止下标越界处理
        if (head == tail) // 检查空间是否够用, == 说明空间不够了
            doubleCapacity(); // 扩容
    }

这里先插入,后扩容。tail总是指向下一个可插入的空位,这个意思就是 数组中至少留有一个空位置,所以元素可以先插入。

head = (head - 1) & (elements.length - 1)这行代码比较难以理解。语义是:取余操作,同时解决head为负值的情况。 elements.length 必定是 2 的指数倍。elements.length - 1的二进制低位必为 1 , 与head - 1进行与操作后,起到了取模的作用(取余数)。如果head - 1为负数(只可能是 -1),则相当于对其取相对于elements.length的补码。

真正的扩容机制在doubleCapacity()

    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

这个函数的作用相当于扩容 100% 后,将原数组,分段复制进去:

首先复制head右侧的元素,然后再把左边的复制过来。即虽然是往队列头部插值,但实际还是在尾部插完值后,分段移动进行排序,最后组成了新数组。

addLast则是直接把新元素存入tail位置上,然后在重新计算tail ,检查是否需要扩容。

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;   //赋值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)   //下标越界处理
        doubleCapacity();   //扩容
}

特点:

  • 不是线程安全的,在没有外部处理同步的情况下,不支持多线程并发访问。
  • 禁止保存null元素。
  • 作为栈使用时,可能比Stack快;作为队列使用时, 比LinkedList快。
  • 时间复杂度时常数级别的。

总结

常见的队列除了 ArrayQueuePriorityQuueue 和BlockingQueue,还有一个可以当作队列的LinkedList,关于它在上一节的 List 体系中有详细的讲解。

  • ArrayQueue,更适用于当作双端队列或栈结构。
  • Stack已不推荐使用,建议使用LinkedListArrayQueue替代。
  • PriorityQueue用来处理优先级,多了一个可自定义优先级条件的能力。
  • BlockingQueue常用于实现 生产者/消费者队列,但线程安全需要外部自己去实现。
  • 上面的几种队列,除了LinkedList,底层的数据结构都是数组。
  • Queue的有些实现没有强制要求不允许存null ,但最好不要存null 。

到此这篇关于Java 集合框架 Queue 和 Stack 体系的文章就介绍到这了,更多相关Java 集合框架 内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java 集合框架 Queue 和 Stack 体系

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Java 集合框架体系总览

集合这块知识的重要性不用多说,加上多线程妥妥的稳占面试必问霸主地主,深入了解集合框架的整体结构以及各个集合类的实现原理是非常有必要的。

Java集合系列之JCF集合框架概述

Java集合框架(Java Collections Framework,JCF)是Java平台提供的一套用于存储、操作和管理对象的集合类库。它包含了一系列接口、抽象类和具体实现类,用于表示和操作不同类型的集合数据结构。JCF提供了一种统一的
2023-09-23

Java集合的总体框架有什么用

这篇文章将为大家详细讲解有关Java集合的总体框架有什么用,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。一、集合概述数组其实就是一个集合。集合实际上就是一个容器。可以来容纳其它的数据。二、集合在开发中的应
2023-06-15

Java 中 Vector 用法在集合框架里的具体定位是怎样的?(java vector用法在集合框架中的定位)

在Java的集合框架中,Vector是一个重要的组件,它具有特定的用途和定位。一、Vector的基本概念Vector是Java集合框架中的一个动态数组类,它类似于数组,但可以根据需要自动调整大小。与数组不同的是,V
Java 中 Vector 用法在集合框架里的具体定位是怎样的?(java vector用法在集合框架中的定位)
Java2024-12-17

Java集合框架和数组的排序是什么

这篇文章将为大家详细讲解有关Java集合框架和数组的排序是什么,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。根据约定,在使用java编程的时候应尽可能的使用现有的类库,当然你也可以自己编写一
2023-06-17

JAVA集合框架中的常用集合及其特点和实现原理简介

本篇内容介绍了“JAVA集合框架中的常用集合及其特点和实现原理简介”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!Java提供的众多集合类由两
2023-06-19

Java集合框架中如何掌握Map和Set 的使用

这篇文章将为大家详细讲解有关Java集合框架中如何掌握Map和Set 的使用,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。1. 搜索1.1 场景引入在学习编程时,我们常见的搜索方式有:直接遍
2023-06-22

Java 集合框架进阶:揭秘 Iterator 和 Iterable 的强大功能

Java 集合框架中的 Iterator 和 Iterable 接口提供了强大的数据遍历和处理功能,本文将深入探讨这两个接口,揭秘它们在数据访问、修改和迭代等方面的应用技巧。
Java 集合框架进阶:揭秘 Iterator 和 Iterable 的强大功能
2024-02-14

Java集合框架项目实战:构建真实世界的应用,体验框架的强大功能

Java集合框架提供的丰富数据结构和算法,使开发人员能够轻松管理和处理数据,本文通过构建真实世界的应用,演示集合框架的强大功能和灵活性。
Java集合框架项目实战:构建真实世界的应用,体验框架的强大功能
2024-02-22

Java中Map集合体系的基本使用和常用API是什么

这篇文章主要讲解了“Java中Map集合体系的基本使用和常用API是什么”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java中Map集合体系的基本使用和常用API是什么”吧!Map集合概述
2023-07-05

Java中的集合框架概述:类和接口详解与数据操作指南

Java中的集合框架是程序员在日常编程中不可或缺的工具之一。它提供了一套灵活、高效的数据结构和算法,用于存储、检索和操作数据
Java中的集合框架概述:类和接口详解与数据操作指南
2024-01-26

Java集合框架面试通关秘籍:攻克算法和数据结构,斩获心仪offer

Java集合框架是Java编程语言中的核心组件,它提供了丰富的集合类型和相关操作,是开发人员构建各种数据结构和算法的基础。在Java面试中,集合框架是考察的重点之一,掌握集合框架的原理和用法,能够帮助你轻松应对面试,斩获心仪offer。
Java集合框架面试通关秘籍:攻克算法和数据结构,斩获心仪offer
2024-02-22

Java集合框架学习资源汇编:精心挑选的教程、书籍和在线课程,助力你的学习之旅

Java集合框架是一个全面的工具集,用于存储、组织和操作数据。本文提供了精心挑选的教程、书籍和在线课程,帮助你快速掌握Java集合框架,成为Java编程高手。
Java集合框架学习资源汇编:精心挑选的教程、书籍和在线课程,助力你的学习之旅
2024-02-22

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录