本篇博客旨在整理记录自已对队列的一些总结，以及刷题的解题思路，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 ?。
本篇文章主要是讲一下基本的队列以及刷题，暂不过多涉及双端、阻塞队列。
文章目录
一、队列的概述二、Java队列的特性三、Java 队列的基本操作四、队列的代码实现4.1、链表实现4.2、数组实现 五、刷题1. 二叉树层序遍历2. 设计循环队列 最后
一、队列的概述
队列(queue) 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品。队列遵循先入先出、后入后出的基本原则。
队列的基本结构：
二、Java队列的特性
队列主要分为阻塞和非阻塞，有界和无界；按功能分：双端队列、优先队列、延迟队列、其他队列
三、Java 队列的基本操作
add(E e)：将元素 e 插入到队列末尾，如果插入成功，则返回 true；如果插入失败（即队列已满），则会抛出异常；remove()：移除队首元素，若移除成功，则返回 true；如果移除失败（队列为空），则会抛出异常；remove(Object o)：移除指定的元素，若移除成功，则返回 true；如果移除失败（队列为空），则会抛出异常；offer(E e)：将元素 e 插入到队列末尾，如果插入成功，则返回 true；如果插入失败（即队列已满），则返回 false；poll()：移除并获取队首元素，若成功，则返回队首元素；否则返回 null；peek()：获取队首元素，若成功，则返回队首元素；否则返回 null；isEmpty()：队列是否为空；size()：队列长度； 四、队列的代码实现
定义一个简化的队列接口：
public interface Queue<E> { /** * 向队列尾插入值 * @param value 待插入值 * @return 插入成功返回 true, 插入失败返回 false */ boolean offer(E value); /** * 从对列头获取值, 并移除 * @return 如果队列非空返回对头值, 否则返回 null */ E poll(); /** * 从对列头获取值, 不移除 * @return 如果队列非空返回对头值, 否则返回 null */ E peek(); /** * 检查队列是否为空 * @return 空返回 true, 否则返回 false */ boolean isEmpty(); /** * 检查队列是否已满 * @return 满返回 true, 否则返回 false */ boolean isFull();}4.1、链表实现
使用单向环形带哨兵链表方式来实现队列
代码：
public class LinkedListQueue<E> implements Queue<E>, Iterable<E> { private static class Node<E> { E value; Node<E> next; public Node(E value, Node<E> next) { this.value = value; this.next = next; } } private Node<E> head = new Node<>(null, null); private Node<E> tail = head; private int size = 0; private int capacity = Integer.MAX_VALUE; { tail.next = head; } public LinkedListQueue() { } public LinkedListQueue(int capacity) { this.capacity = capacity; } @Override public boolean offer(E value) { if (isFull()) { return false; } Node<E> added = new Node<>(value, head); tail.next = added; tail = added; size++; return true; } @Override public E poll() { if (isEmpty()) { return null; } Node<E> first = head.next; head.next = first.next; if (first == tail) { tail = head; } size--; return first.value; } @Override public E peek() { if (isEmpty()) { return null; } return head.next.value; } @Override public boolean isEmpty() { return head == tail; } @Override public boolean isFull() { return size == capacity; } @Override public Iterator<E> iterator() { return new Iterator<E>() { Node<E> p = head.next; @Override public boolean hasNext() { return p != head; } @Override public E next() { E value = p.value; p = p.next; return value; } }; }}4.2、数组实现
环形数组实现好处：
对比普通数组，起点和终点更为自由，不用考虑数据移动；”环“意味着不会存在【越界】问题；数组性能更佳；环形数组比较适合实现有界队列、RingBuffer等；代码：
/* 下标含义： * cur 当前指针位置 * step 前进步数 * length 数组长度 */public class ArrayQueue<E> implements Queue<E>, Iterable<E>{ private int head = 0; private int tail = 0; private final E[] array; private final int length; @SuppressWarnings("all") public ArrayQueue(int capacity) { length = capacity + 1; array = (E[]) new Object[length]; } @Override public boolean offer(E value) { if (isFull()) { return false; } array[tail] = value; tail = (tail + 1) % length; return true; } @Override public E poll() { if (isEmpty()) { return null; } E value = array[head]; head = (head + 1) % length; return value; } @Override public E peek() { if (isEmpty()) { return null; } return array[head]; } @Override public boolean isEmpty() { return tail == head; } @Override public boolean isFull() { return (tail + 1) % length == head; } @Override public Iterator<E> iterator() { return new Iterator<E>() { int p = head; @Override public boolean hasNext() { return p != tail; } @Override public E next() { E value = array[p]; p = (p + 1) % array.length; return value; } }; }}五、刷题
1. 二叉树层序遍历
题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
输入输出样例：
示例一：输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]示例二：输入：root = [1]输出：[[1]]示例三：输入：root = [1]输出：[[1]]提示：
树中节点数目在范围[0, 2000] 内-1000 <= Node.val <= 1000 解题代码：
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if(root == null) { return result; } LinkedListQueue<TreeNode> queue = new LinkedListQueue<>(); queue.offer(root); int c1 = 1;// 本层节点个数 while (!queue.isEmpty()) { int c2 = 0; // 下层节点个数 List<Integer> level = new ArrayList<>(); for (int i = 0; i < c1; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); c2++; } if (node.right != null) { queue.offer(node.right); c2++; } } c1 = c2; result.add(level); } return result; } // 自定义队列 static class LinkedListQueue<E> { private static class Node<E> { E value; Node<E> next; public Node(E value, Node<E> next) { this.value = value; this.next = next; } } private final Node<E> head = new Node<>(null, null); private Node<E> tail = head; int size = 0; private int capacity = Integer.MAX_VALUE; { tail.next = head; } public LinkedListQueue() { } public LinkedListQueue(int capacity) { this.capacity = capacity; } public boolean offer(E value) { if (isFull()) { return false; } Node<E> added = new Node<>(value, head); tail.next = added; tail = added; size++; return true; } public E poll() { if (isEmpty()) { return null; } Node<E> first = head.next; head.next = first.next; if (first == tail) { tail = head; } size--; return first.value; } public E peek() { if (isEmpty()) { return null; } return head.next.value; } public boolean isEmpty() { return head == tail; } public boolean isFull() { return size == capacity; } }}2. 设计循环队列
题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3circularQueue.enQueue(1); // 返回 truecircularQueue.enQueue(2); // 返回 truecircularQueue.enQueue(3); // 返回 truecircularQueue.enQueue(4); // 返回 false，队列已满circularQueue.Rear(); // 返回 3circularQueue.isFull(); // 返回 truecircularQueue.deQueue(); // 返回 truecircularQueue.enQueue(4); // 返回 truecircularQueue.Rear(); // 返回 4提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
解题代码：
class MyCircularQueue { int k, he, ta; int[] nums; public MyCircularQueue(int _k) { k = _k; nums = new int[k]; } public boolean enQueue(int value) { if (isFull()) return false; nums[ta % k] = value; return ++ta >= 0; } public boolean deQueue() { if (isEmpty()) return false; return ++he >= 0; } public int Front() { return isEmpty() ?-1 : nums[he % k]; } public int Rear() { return isEmpty() ? - 1 : nums[(ta - 1) % k]; } public boolean isEmpty() { return he == ta; } public boolean isFull() { return ta - he == k; }}最后
对各位小伙伴有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~???