目录
队列的定义
自实现队列
定义接口
基于链表实现队列
基于数组实现队列
Java中定义的队列接口
LinkedList
底层数据结构
实现了队列特点的方法
LinkedBlockingQueue
底层数据结构
实现了队列特点的方法
LeetCode-102题
题解
测试结果
队列的定义
计算机科学中，队列是以顺序的方式维护的一组数据集合，特点如下
- 在一端添加元素，在另一端移除元素
- 添加元素的一端叫队尾，移除元素的一端叫做队头
- 先进先出
自实现队列
定义接口
首先将接口写好的目的是将它具有哪些能力先定义出来，后续可以用不同的实现方式来具体地将这些功能都实现出来
package algorithm.queue;
/**
* 自定义队列
* 提供接口
*/
public interface CustomQueue {
/**
* 添加元素
*/
boolean offer(Object ele);
/**
* 移除元素并返回
*/
Object poll();
/**
* 只查看元素
*/
Object peek();
/**
* 元素个数
*/
int size();
/**
* 是否为空
*/
boolean isEmpty();
}
基于链表实现队列
package algorithm.queue;
import java.util.Iterator;
import java.util.function.Consumer;
/**
* 基于链表实现队列
* 本类中提供两种遍历队列中元素的方式：
* 1、通过Consumer函数式接口，将元素提供给调用方
* 2、使该类具有增强for的能力
*/
public class CustomLinkedListQueue implements CustomQueue, Iterable<Object> {
//定义虚拟节点
private final Node dummyHead = new Node();
private final Node dummyTail = new Node();
// 元素个数
private int size;
// 构造器中初始化头尾节点的关系
public CustomLinkedListQueue() {
initHeadAndTailNode();
}
private void initHeadAndTailNode() {
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
@Override
public boolean offer(Object ele) {
if (ele == null) {
throw new NullPointerException();
}
addLast(ele);
return true;
}
/**
* 尾部添加元素
*/
private void addLast(Object ele) {
Node node = new Node(ele);
Node prev = dummyTail.prev;
dummyTail.prev = node;
node.prev = prev;
node.next = dummyTail;
prev.next = node;
size++;
}
@Override
public Object poll() {
Object result = peek();
if (result != null) {
removeFirst();
}
return result;
}
/**
* 删除头部元素节点
*/
private void removeFirst() {
Node removeNode = dummyHead.next;
Node next = dummyHead.next.next;
dummyHead.next = next;
next.prev = dummyHead;
removeNode.next = null;
removeNode.prev = null;
size–;
}
@Override
public Object peek() {
if (isEmpty()) {
return null;
}
return dummyHead.next.val;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 遍历元素：将元素交给调用方
*/
public void foreach(Consumer<Object> consumer) {
Node p = dummyHead.next;
while (p != dummyTail) {
consumer.accept(p.val);
p = p.next;
}
}
/**
* 提供增强for能力
*/
@Override
public Iterator<Object> iterator() {
return new Iterator<Object>() {
Node p = dummyHead.next;
@Override
public boolean hasNext() {
return p != dummyTail;
}
@Override
public Object next() {
Node node = p;
p = p.next;
return node.val;
}
};
}
/**
* 定义数据节点
*/
private static class Node {
Object val;
Node prev;
Node next;
public Node() {
}
public Node(Object val) {
this.val = val;
}
public Node(Object val, Node prev, Node next) {
this.val = val;
this.prev = prev;
this.next = next;
}
}
}
基于数组实现队列
package algorithm.queue;
import java.util.Arrays;
import java.util.Iterator;
/**
* 基于数组实现队列
* 本类中提供两种遍历队列中元素的方式：
* 1、重写toString() -> 将队列中所有元素拼接成字符串返回，格式：[1,2,3]
* 2、使该类具有增强for的能力
*/
public class CustomArrayQueue implements CustomQueue, Iterable<Object> {
private int size;
private Object[] container;
private static final int DEFAULT_INIT_CAPACITY = 10;
private static final int MAX_CAPACITY = 1024;
public CustomArrayQueue() {
}
@Override
public boolean offer(Object ele) {
// 前置准备
checkOrInit(ele);
// 判断扩容条件和执行扩容操作
grow(size + 1);
// 存入元素
container[size++] = ele;
return true;
}
private void checkOrInit(Object ele) {
if (ele == null) {
throw new NullPointerException();
}
if (isFull()) {
throw new RuntimeException("队列已满");
}
if (isEmpty()) {
container = new Object[DEFAULT_INIT_CAPACITY];
}
}
private void grow(int minCapacity) {
int oldCapacity = container.length;
if (minCapacity <= oldCapacity) {
return;
}
int newCapacity = oldCapacity + (oldCapacity >> 1);
newCapacity = Math.max(minCapacity, newCapacity);
newCapacity = Math.min(MAX_CAPACITY, newCapacity);
container = Arrays.copyOf(container, newCapacity);
}
private boolean isFull() {
return size == MAX_CAPACITY;
}
@Override
public Object poll() {
Object ele = peek();
if (ele == null) {
return null;
}
System.arraycopy(container, 1, container, 0, (size – 1));
size–;
container[size] = null;//help gc
return ele;
}
@Override
public Object peek() {
if (isEmpty()) {
return null;
}
return container[0];
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 将队列中的元素遍历出来(拼接返回)
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder("[");
for (int i = 0; i < size; i++) {
builder.append(container[i]);
if (i != size – 1) {
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
/**
* 是队列具有增强for能力
*/
@Override
public Iterator<Object> iterator() {
return new Iterator<Object>() {
int index = 0;
@Override
public boolean hasNext() {
return index < size;
}
@Override
public Object next() {
return container[index++];
}
};
}
}
Java中定义的队列接口
package java.util;
// …
public interface Queue<E> extends Collection<E> {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
LinkedList
基于双向链表实现的集合框架，实现了Queue接口和Deque，可以用作队列或双端队列
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
public interface Deque<E> extends Queue<E>
{}
底层数据结构
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// …
transient Node<E> first;
transient Node<E> last;
// 数据节点
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// …
}
实现了队列特点的方法
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// …
public boolean offer(E e) {
// …
}
public E poll() {
// …
}
public E peek() {
// …
}
// …
}
LinkedBlockingQueue
基于单向链表实现的阻塞队列，实现了BlockingQueue接口
public class LinkedBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
}
底层数据结构
package java.util.concurrent;
// …
public class LinkedBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
// …
// 数据节点
static class Node<E> {
E item;
Node<E> next;
Node(E x) { item = x; }
}
// …
}
实现了队列特点的方法
package java.util.concurrent;
// …
public class LinkedBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
// …
// 入队：当队列满时阻塞等待
public void put(E e) throws InterruptedException {
// …
}
// 入队：当队列满时阻塞等待，最多等待指定时间
public boolean offer(E e, long timeout, TimeUnit unit)
// …
}
// 入队：不阻塞等待，队列满时直接返回
public boolean offer(E e) {
// …
}
// 出队：当队列空时阻塞等待
public E take() throws InterruptedException {
// …
}
// 出队：当队列空时阻塞等待，最多等待指定时间
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
// …
}
// 出队：不阻塞等待，队列空时直接返回
public E poll() {
// …
}
// …
}
LeetCode-102题
题解
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
// 使用队列协助解题
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点入队
queue.offer(root);
// 记录当前层节点个数
int c1 = 1;
while (!queue.isEmpty()) {
List<Integer> inner = new ArrayList<>();
// 记录下一层节点个数
int c2 = 0;
for (int i = 0; i < c1; i++) {
TreeNode currNode = queue.poll();
inner.add(currNode.val);
if (currNode.left != null) {
queue.offer(currNode.left);
c2++;
}
if (currNode.right != null) {
queue.offer(currNode.right);
c2++;
}
}
result.add(inner);
c1 = c2;
}
return result;
}
}
测试结果
