数据结构和算法之【队列】

目录队列的定义自实现队列定义接口基于链表实现队列基于数组实现队列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, IterableObject { //定义虚拟节点 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(ConsumerObject consumer) { Node p dummyHead.next; while (p ! dummyTail) { consumer.accept(p.val); p p.next; } } /** * 提供增强for能力 */ Override public IteratorObject iterator() { return new IteratorObject() { 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, IterableObject { 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 IteratorObject iterator() { return new IteratorObject() { int index 0; Override public boolean hasNext() { return index size; } Override public Object next() { return container[index]; } }; } }Java中定义的队列接口package java.util; // ... public interface QueueE extends CollectionE { boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); }LinkedList基于双向链表实现的集合框架实现了Queue接口和Deque可以用作队列或双端队列public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable {} public interface DequeE extends QueueE {}底层数据结构package java.util; import java.util.function.Consumer; public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable { // ... transient NodeE first; transient NodeE last; // 数据节点 private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } } // ... }实现了队列特点的方法package java.util; import java.util.function.Consumer; public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable { // ... public boolean offer(E e) { // ... } public E poll() { // ... } public E peek() { // ... } // ... }LinkedBlockingQueue基于单向链表实现的阻塞队列实现了BlockingQueue接口public class LinkedBlockingQueueE extends AbstractQueueE implements BlockingQueueE, java.io.Serializable { }底层数据结构package java.util.concurrent; // ... public class LinkedBlockingQueueE extends AbstractQueueE implements BlockingQueueE, java.io.Serializable { // ... // 数据节点 static class NodeE { E item; NodeE next; Node(E x) { item x; } } // ... }实现了队列特点的方法package java.util.concurrent; // ... public class LinkedBlockingQueueE extends AbstractQueueE implements BlockingQueueE, 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 ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } // 使用队列协助解题 QueueTreeNode queue new LinkedList(); // 将根节点入队 queue.offer(root); // 记录当前层节点个数 int c1 1; while (!queue.isEmpty()) { ListInteger 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; } }测试结果