队列-我的基础算法刷题之路（六）

news/2025/1/17 21:37:08/

在这里插入图片描述

本篇博客旨在整理记录自已对队列的一些总结，以及刷题的解题思路，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 💪。
本篇文章主要是讲一下基本的队列以及刷题，暂不过多涉及双端、阻塞队列。

文章目录

    • 一、队列的概述
    • 二、Java队列的特性
    • 三、Java 队列的基本操作
    • 四、队列的代码实现
      • 4.1、链表实现
      • 4.2、数组实现
    • 五、刷题
      • 1. 二叉树层序遍历
      • 2. 设计循环队列
    • 最后

一、队列的概述

队列(queue) 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品。队列遵循先入先出、后入后出的基本原则。

队列的基本结构：

1
2
3
4
进队
出队

二、Java队列的特性

队列主要分为阻塞和非阻塞，有界和无界；按功能分：双端队列、优先队列、延迟队列、其他队列

Queue
按阻塞分类
按大小分类
按功能分类
阻塞队列
非阻塞队列
有界队列
无界队列
普通队列
优先队列
双端队列
延迟队列
其他队列

三、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;}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}Node<E> added = new Node<>(value, head);tail.next = added;tail = added;size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}Node<E> first = head.next;head.next = first.next;if (first == tail) {tail = head;}size--;return first.value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return size == capacity;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = head.next;@Overridepublic boolean hasNext() {return p != head;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}
}

4.2、数组实现

环形数组实现好处：

  1. 对比普通数组，起点和终点更为自由，不用考虑数据移动；
  2. ”环“意味着不会存在【越界】问题；
  3. 数组性能更佳；
  4. 环形数组比较适合实现有界队列、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];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] = value;tail = (tail + 1) % length;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}E value = array[head];head = (head + 1) % length;return value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}@Overridepublic boolean isEmpty() {return tail == head;}@Overridepublic boolean isFull() {return (tail + 1) % length == head;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = head;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic 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); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.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;}
}

最后

对各位小伙伴有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌


http://www.ppmy.cn/news/35201.html

相关文章

Kotlin~Adapter适配器模式

Kotlin~Adapter适配器模式

概念 Adapter&#xff08;Wrapper&#xff09; Pattern&#xff0c;连接两个不兼容的接口&#xff0c;让接口不兼容的对象能够相互合作。 适配器中的角色 请求者Client&#xff1a;调用者目标Target&#xff1a;定义了Client要使用的功能转化对象Adaptee&#xff1a; 需要适…
阅读更多...
Java反射机制

Java反射机制

1.定义java的反射&#xff08;reflection&#xff09;机制是在java运行状态中&#xff0c;对任意一个类&#xff0c;都能知道这个类的所有方法和属性。 对于任意一个对象&#xff0c; 都能够调用它的任意方法和属性&#xff0c; 也可以修改其部分信息。 这种动态获取值以及动态…
阅读更多...
【Vue3】用Element Plus实现列表界面

【Vue3】用Element Plus实现列表界面

&#x1f3c6;今日学习目标&#xff1a;用Element Plus实现列表界面 &#x1f603;创作者&#xff1a;颜颜yan_ ✨个人格言&#xff1a;生如芥子&#xff0c;心藏须弥 ⏰本期期数&#xff1a;第四期 &#x1f389;专栏系列&#xff1a;Vue3 文章目录前言效果图目录简介修改vite…
阅读更多...
Java的基础面试题

Java的基础面试题

一.java基础1.JDK和JRE有什么区别&#xff1f;JDK是java开发工具包&#xff0c;JRE是java运行时环境&#xff08;包括Java基础类库&#xff0c;java虚拟机&#xff09;2.和equals的区别是什么&#xff1f;比较的是两者的地址值&#xff0c;equals比较的是两者的内容是否一样3.两…
阅读更多...
Python和Excel的完美结合:常用操作汇总(案例详析)

Python和Excel的完美结合:常用操作汇总(案例详析)

在以前&#xff0c;商业分析对应的英文单词是Business Analysis&#xff0c;大家用的分析工具是Excel&#xff0c;后来数据量大了&#xff0c;Excel应付不过来了&#xff08;Excel最大支持行数为1048576行&#xff09;&#xff0c;人们开始转向python和R这样的分析工具了&#…
阅读更多...
内核线程与用户线程的区别

内核线程与用户线程的区别

内核线程和用户线程是操作系统中的两种不同类型的线程&#xff0c;它们有以下异同点&#xff1a; 异同点&#xff1a; 相同点&#xff1a;内核线程和用户线程都是线程的一种&#xff0c;都可以执行任务。 不同点&#xff1a;内核线程是由操作系统内核创建和管理的&#xff0c…
阅读更多...
举一反三学python(5)—初识数组

举一反三学python(5)—初识数组

一、引例 大家对MBI&#xff08;身体质量指数&#xff09;都有所了解吧&#xff01; MBI&#xff08;身体质量指数&#xff09; MBI指数计算方法为体重除以身高的平方&#xff0c;其中体重的单位为千克&#xff0c;身高的单位为米。 正常中国人的BMI范围区间在…
阅读更多...
Prometheus cadvisor容器监控和node-exporter节点监控

Prometheus cadvisor容器监控和node-exporter节点监控

往期文章 Prometheus监控系统 https://blog.csdn.net/qq_39578545/article/details/108754585 Docker之compose介绍 使用一个Dockerfile模板文件可以定义一个单独的应用容器&#xff0c;如果需要定义多个容器就需要服务编排。下面介绍Docker官方产品&#xff0c;Docker Comp…
阅读更多...
最新文章

Copyright @ 2022~2023