本文共 2414 字，大约阅读时间需要 8 分钟。

线性数据结构

队列

队列是一种遵循先进先出（FIFO）原则的数据集合，数据在队列中的流动是单向的，从队尾流向队首。

Queue接口

Queue是标准的集合接口，包含以下关键方法：

• boolean add(E e)：将元素添加到队列中。如果没有空间，会抛出IllegalStateException。
• boolean offer(E e)：尝试将元素添加到队列末尾，不影响其他操作。
• E remove()：从队列头部移除并返回元素，队列为空时抛出NoSuchElementException。
• E poll()：从队列头部移除并返回元素，队列为空时返回null。
• E element()：从队列头部返回元素，但不移除，队列为空时抛出NoSuchElementException。
• E peek()：从队列头部查看元素，队列为空时返回null。

双端队列（Deque）

Deque是一种双端队列，允许在队列的两个端点进行入队和出队操作。

Deque接口

Deque接口继承自Queue，增加了以下功能：

• void addFirst(E e)：将元素添加到队列的前部。
• void addLast(E e)：将元素添加到队列的后部。
• boolean offerFirst(E e)：尝试将元素添加到队列的前部。
• boolean offerLast(E e)：尝试将元素添加到队列的后部。
• E removeFirst()：移除并返回队列前部的元素，队列为空时返回null。
• E removeLast()：移除并返回队列后部的元素，队列为空时返回null。
• E pollFirst()：移除并返回队列前部的元素，队列为空时返回null。
• E pollLast()：移除并返回队列后部的元素，队列为空时返回null。
• E getFirst()：返回队列前部的元素，队列为空时返回null。
• E getLast()：返回队列后部的元素，队列为空时返回null。
• E peekFirst()：查看队列前部的元素，队列为空时返回null。
• E peekLast()：查看队列后部的元素，队列为空时返回null。
• boolean removeFirstOccurrence(Object o)：移除队列中首次出现的指定元素。
• boolean removeLastOccurrence(Object o)：移除队列中最后一次出现的指定元素。

LinkedList类

双向链表

LinkedList实现了双向链表，其核心成员变量包括：

• first：队列的头节点。
• last：队列的尾节点。

Node类

Node是链表的基本节点，包含以下成员变量：

• item：存储元素值。
• next：指向下一个节点。
• prev：指向上一个节点。

插入元素

公共方法

• boolean add(E e)：通过调用linkLast(e)添加元素。
• boolean offer(E e)：通过调用add(e)添加元素，并返回true。

添加到末尾

public boolean offer(E e) {    return add(e);}public boolean add(E e) {    linkLast(e);    return true;}private void linkLast(E e) {    final Node l = last;    final Node newNode = new Node(l, e, null);    last = newNode;    if (l == null) {        first = newNode;    } else {        l.next = newNode;    }    size++;    modCount++;}

添加到前端

public boolean offerFirst(E e) {    return addFirst(e);}public void addFirst(E e) {    linkFirst(e);}private void linkFirst(E e) {    final Node f = first;    final Node newNode = new Node(null, e, f);    first = newNode;    if (f == null) {        last = newNode;    } else {        f.prev = newNode;    }    size++;    modCount++;}

删除元素

公共方法

• public E poll()：从头部移除元素。
• public E pollFirst()：从头部移除并返回元素。

移除头部节点

public E poll() {    final Node f = first;    return (f == null) ? null : unlinkFirst(f);}public E pollFirst() {    return unlinkFirst(first);}private E unlinkFirst(Node f) {    final E element = f.item;    final Node next = f.next;    f.item = null;    f.next = null;    first = next;    if (next == null) {        last = null;    } else {        next.prev = null;    }    size--;    modCount++;    return element;}

转载地址：http://jfryk.baihongyu.com/