java-数据结构与算法-02-数据结构-06-双端队列

1. 概述

双端队列、队列、栈对比

在这里插入图片描述

注1：

  • Java 中 LinkedList 即为典型双端队列实现，不过它同时实现了 Queue 接口，也提供了栈的 push pop 等方法

注2：

  • 不同语言，操作双端队列的方法命名有所不同，参见下表

在这里插入图片描述
接口定义

/*** 双端队列接口* 双端队列是一种可以在其两端进行添加和移除元素的线性数据结构。* 该接口定义了在队列的首端和尾端进行操作的方法。* @param <E> 队列中元素的类型*/
/*** 双端队列接口* @param <E> 队列中元素类型*/
public interface Deque<E> {/*** 在队列的首端添加一个元素。* @param e 要添加到队列首端的元素* @return 如果成功添加元素，则返回true；否则返回false*/boolean offerFirst(E e);/*** 在队列的尾端添加一个元素。* @param e 要添加到队列尾端的元素* @return 如果成功添加元素，则返回true；否则返回false*/boolean offerLast(E e);/*** 从队列的首端移除一个元素。* @return 队列首端的元素；如果队列为空，则返回null*/E pollFirst();/*** 从队列的尾端移除一个元素。* @return 队列尾端的元素；如果队列为空，则返回null*/E pollLast();/*** 获取队列的首端元素，但不移除它。* @return 队列首端的元素；如果队列为空，则返回null*/E peekFirst();/*** 获取队列的尾端元素，但不移除它。* @return 队列尾端的元素；如果队列为空，则返回null*/E peekLast();/*** 检查队列是否为空。* @return 如果队列为空，则返回true；否则返回false*/boolean isEmpty();/*** 检查队列是否已满。* 注意：具体实现可能需要定义队列的容量限制。如果没有预定义的容量限制，则该方法总是返回false。* @return 如果队列已满，则返回true；否则返回false*/boolean isFull();
}

2. 链表实现

/*** 双向队列的链表实现。* 基于双向环形链表实现的双端队列，支持在队列的首尾位置进行添加和移除元素的操作。* * @param <E> 队列中元素的类型。*/
package com.itheima.datastructure.deque;import java.util.Iterator;/*** 双向队列的链表实现类。*/
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {/*** 队列中元素的节点类。*/static class Node<E> {Node<E> prev;E value;Node<E> next;public Node(Node<E> prev, E value, Node<E> next) {this.prev = prev;this.value = value;this.next = next;}}int capacity; // 队列的容量int size; // 队列中当前元素的数量Node<E> sentinel = new Node<>(null, null, null); // 队列的哨兵节点，用于简化链表操作/*** 构造一个具有指定容量的双向队列。* * @param capacity 队列的容量。*/public LinkedListDeque(int capacity) {this.capacity = capacity;sentinel.next = sentinel;sentinel.prev = sentinel;}
}/*** 在队列首部添加一个元素。* * @param e 要添加的元素。* @return 如果队列未满，则添加成功并返回true；否则，添加失败并返回false。*/@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}Node<E> a = sentinel;Node<E> b = sentinel.next;Node<E> added = new Node<>(a, e, b);a.next = added;b.prev = added;size++;return true;}/*** 在队列尾部添加一个元素。* * @param e 要添加的元素。* @return 如果队列未满，则添加成功并返回true；否则，添加失败并返回false。*/@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}Node<E> a = sentinel.prev;Node<E> b = sentinel;Node<E> added = new Node<>(a, e, b);a.next = added;b.prev = added;size++;return true;}/*** 从队列首部移除一个元素。* * @return 如果队列不为空，则移除队列首部的元素并返回；否则，返回null。*/@Overridepublic E pollFirst() {if (isEmpty()) {return null;}Node<E> a = sentinel;Node<E> removed = sentinel.next;Node<E> b = removed.next;a.next = b;b.prev = a;size--;return removed.value;}/*** 从队列尾部移除一个元素。* * @return 如果队列不为空，则移除队列尾部的元素并返回；否则，返回null。*/@Overridepublic E pollLast() {if (isEmpty()) {return null;}Node<E> b = sentinel;Node<E> removed = sentinel.prev;Node<E> a = removed.prev;a.next = b;b.prev = a;size--;return removed.value;}/*** 获取队列首部的元素，但不移除。* * @return 如果队列不为空，则返回队列首部的元素；否则，返回null。*/@Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}/*** 获取队列尾部的元素，但不移除。* * @return 如果队列不为空，则返回队列尾部的元素；否则，返回null。*/@Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}/*** 检查队列是否为空。* * @return 如果队列为空，则返回true；否则，返回false。*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 检查队列是否已满。* * @return 如果队列已满，则返回true；否则，返回false。*/@Overridepublic boolean isFull() {return size == capacity;}/*** 返回队列的迭代器，用于遍历队列中的元素。* * @return 队列的迭代器。*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}

3. 数组实现

package com.itheima.datastructure.deque;import java.util.Iterator;/*** 循环数组双端队列的实现。* <p>* 特点：* - 使用循环数组为基础进行实现。* - 当尾指针追赶上头指针时，队列被认为是满的。* - 头指针和尾指针的移动通过取模运算实现循环。** @param <E> 队列中元素的类型。*/
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {/*** 计算头指针的下一个位置。** @param i 当前头指针的位置。* @param length 数组的长度。* @return 头指针的下一个位置。*/static int inc(int i, int length) {if (i + 1 >= length) {return 0;}return i + 1;}/*** 计算尾指针的上一个位置。** @param i 当前尾指针的位置。* @param length 数组的长度。* @return 尾指针的上一个位置。*/static int dec(int i, int length) {if (i - 1 < 0) {return length - 1;}return i - 1;}/*** 在队列首部添加一个元素。** @param e 要添加的元素。* @return 如果队列未满，则返回true；否则返回false。*/@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head = dec(head, array.length);array[head] = e;return true;}/*** 在队列尾部添加一个元素。** @param e 要添加的元素。* @return 如果队列未满，则返回true；否则返回false。*/@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] = e;tail = inc(tail, array.length);return true;}/*** 从队列首部移除并返回一个元素。** @return 队列首部的元素，如果队列为空，则返回null。*/@Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e = array[head];array[head] = null; // 帮助垃圾回收head = inc(head, array.length);return e;}/*** 从队列尾部移除并返回一个元素。** @return 队列尾部的元素，如果队列为空，则返回null。*/@Overridepublic E pollLast() {if (isEmpty()) {return null;}tail = dec(tail, array.length);E e = array[tail];array[tail] = null; // 帮助垃圾回收return e;}/*** 返回队列首部的元素，但不移除。** @return 队列首部的元素，如果队列为空，则返回null。*/@Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}/*** 返回队列尾部的元素，但不移除。** @return 队列尾部的元素，如果队列为空，则返回null。*/@Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}/*** 检查队列是否为空。** @return 如果队列为空，则返回true；否则返回false。*/@Overridepublic boolean isEmpty() {return head == tail;}/*** 检查队列是否已满。** @return 如果队列已满，则返回true；否则返回false。*/@Overridepublic boolean isFull() {if (tail > head) {return tail - head == array.length - 1;} else if (tail < head) {return head - tail == 1;} else {return false;}}/*** 获取队列的迭代器，用于遍历队列元素。** @return 队列元素的迭代器。*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = head;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic E next() {E e = array[p];p = inc(p, array.length);return e;}};}E[] array;int head;int tail;/*** 构造函数，初始化队列。** @param capacity 队列的容量。*/@SuppressWarnings("all")public ArrayDeque1(int capacity) {array = (E[]) new Object[capacity + 1];}
}

数组实现中，如果存储的是基本类型，那么无需考虑内存释放，例如

在这里插入图片描述
但如果存储的是引用类型，应当设置该位置的引用为 null，以便内存及时释放
在这里插入图片描述

习题

E01. 二叉树 Z 字层序遍历-Leetcode 103

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例1：
在这里插入图片描述
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

在这里插入图片描述

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

题解：
利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：

  • 奇数层 则添加至 tmp 尾部 ，
  • 偶数层 则添加至 tmp 头部 。

算法流程：

  1. 特例处理： 当树的根节点为空，则直接返回空列表 [] 。
  2. 初始化： 打印结果空列表 res ，包含根节点的双端队列 deque 。
  3. BFS 循环： 当 deque 为空时跳出。
    • 新建列表 tmp ，用于临时存储当前层打印结果。
    • 当前层打印循环： 循环次数为当前层节点数（即 deque 长度）。
      • 出队： 队首元素出队，记为 node。
      • 打印： 若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部。
      • 添加子节点： 若 node 的左（右）子节点不为空，则加入 deque 。
    • 将当前层结果 tmp 转化为 list 并添加入 res 。
  4. 返回值： 返回打印结果列表 res 即可。

在这里插入图片描述

/*** 对二叉树进行锯齿形层次遍历，并返回结果列表。* 锯齿形层次遍历的特点是，每个层级的元素在结果列表中交替地从前向后和从后向前排列。* * @param root 二叉树的根节点* @return 包含锯齿形层次遍历结果的列表*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {/* 使用队列来辅助进行层次遍历 */Queue<TreeNode> queue = new LinkedList<>();/* 用于存储最终的遍历结果 */List<List<Integer>> res = new ArrayList<>();/* 如果根节点不为空，则将其加入队列 */if (root != null) queue.add(root);/* 当队列不为空时，继续遍历 */while (!queue.isEmpty()) {/* 使用双端队列来存储当前层级的节点值，以便实现锯齿形排列 */LinkedList<Integer> tmp = new LinkedList<>();/* 遍历当前层级的所有节点 */for(int i = queue.size(); i > 0; i--) {/* 从队列中取出一个节点 */TreeNode node = queue.poll();/* 根据当前层级的索引，决定节点值是添加到队列的前端还是后端 */if (res.size() % 2 == 0) tmp.addLast(node.val);else tmp.addFirst(node.val);/* 如果节点有左子节点，则将左子节点加入队列 */if (node.left != null) queue.add(node.left);/* 如果节点有右子节点，则将右子节点加入队列 */if (node.right != null) queue.add(node.right);}/* 将当前层级的节点值列表加入到结果中 */res.add(tmp);}/* 返回最终的遍历结果 */return res;
}

Ex1. 设计双端队列-Leetcode 641

实现 MyCircularDeque 类:

MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront())：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：

输入
[“MyCircularDeque”, “insertLast”, “insertLast”, “insertFront”, “insertFront”, “getRear”, “isFull”, “deleteLast”, “insertFront”, “getFront”]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2 circularDeque.isFull();
// 返回 true circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4

提示：

1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast,deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于
2000 次

与例题也是差别不大，略

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/387165.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

day05 Router、vuex、axios

day05 Router、vuex、axios

配置 router和vuex需要在创建vue项目的时候&#xff0c;开始的时候选择Manually select features&#xff0c;于是就可以在下一个创建配置讯问中选择router和vuex。 axios则需要执行命令行&#xff1a; npm install axios -S 之后再在需要发送请求的view导入即可。 router…
阅读更多...
Chapter 20 Python包

Chapter 20 Python包

欢迎大家订阅【Python从入门到精通】专栏&#xff0c;一起探索Python的无限可能&#xff01; 文章目录 前言一、自定义包1. 什么是Python包&#xff1f;2. 目录结构3. 导入方式4. __all__变量 二、第三方包1. 什么是第三方包&#xff1f;2. 安装第三方包 前言 在 Python 中&am…
阅读更多...
PHP反序列化漏洞

PHP反序列化漏洞

一.PHP的序列化和反序列化 &#xff08;1&#xff09;.作用 PHP的序列化和反序列化是PHP中用于存储或传输PHP的值的一个过程。序列化是将变量转换为可存储或传输的字符串的过程&#xff0c;而反序列化则是将这些字符串转换回PHP变量的过程。这两个过程在PHP开发中非常有用&am…
阅读更多...
vue element-ui日期控件传参

vue element-ui日期控件传参

前端&#xff1a;Vue element-ui <el-form-item label"过期时间" :rules"[ { required: true, message: 请选择过期时间, trigger: blur }]"><el-date-picker v-model"form.expireTime" type"date" format"yyyy-MM-dd&…
阅读更多...
Linux--序列化与反序列化

Linux--序列化与反序列化

序列化 序列化是指将数据结构或对象状态转换成可以存储或传输的格式的过程。在序列化过程中&#xff0c;对象的状态信息被转换为可以保持或传输的格式&#xff08;如二进制、XML、JSON等&#xff09;。序列化后的数据可以被写入到文件、数据库、内存缓冲区中&#xff0c;或者通…
阅读更多...
当年很流行，现在已经淘汰的Java技术，请不要学了！【建议收藏】

当年很流行，现在已经淘汰的Java技术，请不要学了！【建议收藏】

在Java技术的发展历程中&#xff0c;确实有一些曾经流行但现在已经被淘汰或不再推荐使用的技术。了解这些技术可以帮助你避免学习过时的知识&#xff0c;从而更高效地提升自己的技能。 以下是一些曾经流行但现在已经不太推荐学习的Java技术&#xff1a; 1. Servlet 2.x&#x…
阅读更多...
谷粒商城实战笔记-71-商品服务-API-属性分组-前端组件抽取父子组件交互

谷粒商城实战笔记-71-商品服务-API-属性分组-前端组件抽取父子组件交互

文章目录 一&#xff0c;一次性创建所有的菜单二&#xff0c;开发属性分组界面1&#xff0c;左侧三级分类树形组件2&#xff0c;右侧分组列表3&#xff0c;左右两部分通信3.1 子组件发送数据3.2&#xff0c;父组件接收数据 Vue的父子组件通信父组件向子组件传递数据子组件向父组…
阅读更多...
【odoo17】后端py方法触发右上角提示组件

【odoo17】后端py方法触发右上角提示组件

概要 在前面文章中&#xff0c;有介绍过前端触发的通知服务。 【odoo】右上角的提示&#xff08;通知服务&#xff09; 此文章则介绍后端触发方法。 内容 直接上代码&#xff1a;但是前提一定是按钮触发&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; def bu…
阅读更多...
自动化测试 pytest 中 scope 限制 fixture使用范围！

自动化测试 pytest 中 scope 限制 fixture使用范围！

导读 fixture 是 pytest 中一个非常重要的模块&#xff0c;可以让代码更加简洁。 fixture 的 autouse 为 True 可以自动化加载 fixture。 如果不想每条用例执行前都运行初始化方法(可能多个fixture)怎么办&#xff1f;可不可以只运行一次初始化方法&#xff1f; 答&#xf…
阅读更多...
17.延迟队列

17.延迟队列

介绍 延迟队列&#xff0c;队列内部是有序的&#xff0c;延迟队列中的元素是希望在指定时间到了以后或之前取出和处理。 死信队列中&#xff0c;消息TTL过期的情况其实就是延迟队列。 使用场景 1.订单在十分钟内未支付则自动取消。 2.新创建的店铺&#xff0c;如果十天内没…
阅读更多...
【Ant Design Vue的更新日志】

【Ant Design Vue的更新日志】

🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者，CSDN实力新星，CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 以下是Ant Design Vue的更新日志 版本1.7.0（发布日期：2023年4月） …
阅读更多...
TCP/IP协议——使用Socket套接字实现

TCP/IP协议——使用Socket套接字实现

目录 Socket 使用Socket实现TCP客户端和服务器的过程 使用Socket搭建TCP服务器 线程优化 向客户端发送消息 连接的断开 客户端主动断开 服务端主动断开 服务器完整的程序 使用Socket编写客户端程序连接TCP服务器 Socket Socket是一种网络通信协议&#xff0c;它允许…
阅读更多...
渗透测试：筑牢网络安全的坚固防线

渗透测试：筑牢网络安全的坚固防线

在当今这个互联网高度发达的时代&#xff0c;网络安全已成为维护社会稳定和经济发展的重要基石。随着互联网的普及&#xff0c;网络攻击手段日益复杂多变&#xff0c;各类安全威胁层出不穷。为了有效应对这些挑战&#xff0c;渗透测试作为一种重要的安全测试与评估方法&#xf…
阅读更多...
arduino程序-数字输出-学用led（led电路及相关函数）（基础知识）

arduino程序-数字输出-学用led（led电路及相关函数）（基础知识）

arduino程序-数字输出-学用led&#xff08;led电路及相关函数&#xff09;&#xff08;基础知识&#xff09; 1-10 数字输出1-学用ledLED发光二极管LED电压特性电阻 1-11 数字输出arduino控制LEDLed与arduino连接电路图高电平及低电平含义 1-10 数字输出1-学用led 元器件初步介…
阅读更多...
Android Studio的新界面，怎么切换回老界面

Android Studio的新界面，怎么切换回老界面

将勾选的 Enable new UI 取消掉即可
阅读更多...
关于 AGGLIGATOR（猛禽）网络宽频聚合器

关于 AGGLIGATOR（猛禽）网络宽频聚合器

AGGLIGATOR 是一个用于多个链路UDP/IP带宽聚合的工具软件&#xff0c;类似MTCP的作用&#xff0c;不过它是针对UDP/IP宽频聚合的。 举个例子&#xff1a; 中国大陆有三台公网服务器&#xff0c;中国香港有一台大带宽服务器。 那么&#xff1a; AGGLIGATOR 允许中国大陆的客户…
阅读更多...
Day7-指针专题二

Day7-指针专题二

1. 字符指针与字符串 C语言通过使用字符数组来处理字符串 通常&#xff0c;我们把char数据类型的指针变量称为字符指针变量。字符指针变量与字符数组有着密切关系&#xff0c;它也被用来处理字符串 初始化字符指针是把内存中字符串的首地址赋予指针&#xff0c;并不是把该字符串…
阅读更多...
独占电脑资源来执行一个应用

独占电脑资源来执行一个应用

1. 背景 在人工智能时代&#xff0c;随着神经网络的发展&#xff0c;训练人工智能模型需要越来越多的硬件资源&#xff0c;例如&#xff0c;利用10万条棋局数据、使用一台PC电脑、完整地训练一次确定性神经网络五子棋模型&#xff0c;需要花费一年半的时间。随着训练数据的增长…
阅读更多...
＜PLC＞＜HMI＞＜汇川＞在汇川HMI画面中，如何为UI设置全局样式？

＜PLC＞＜HMI＞＜汇川＞在汇川HMI画面中，如何为UI设置全局样式？

前言 汇川的HMI软件是使用了Qt来编写的，因此在汇川的HMI程序编写过程，是支持使用qt的样式来自定义部件样式的，即qss格式。 概述 汇川的软件本身提供三个系统的style样式，我们可以直接使用，但是，如果系统提供的样式不符合你的需求，那么你可以对其进行修改，或者自己新建…
阅读更多...
进程间通信与线程间通信的方法汇总

进程间通信与线程间通信的方法汇总

目录 一、进程间通信机制 管道(pipe)&#xff1a; 命名管道(FIFO)&#xff1a; 消息队列(MQ)&#xff1a; 信号量(semaphore)&#xff1a; 共享内存(shared memory)&#xff1a; 信号(signal)&#xff1a; 内存映射(mapped memory)&#xff1a; 内存映射和共享内存的区…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023