基础数据结构——队列(链表实现)

server/2024/11/14 4:37:23/

队列的性质

  • 先进先出(FIFO - First In First Out):最先加入队列的元素最先被移出
  • 后进后出(后来的元素排在队尾)
  • 只允许在队尾插入元素,在队首删除元素
  • 具有先来先服务的特点

链表实现队列

和之前创建链表相同,我们需要设置一个哨兵头结点 此时它既是head也是tail

后面进行添加操作的之后将每次新加的节点设置为tail,并且指向head

我们接下来实现队列的基本操作

先来写队列类和它内部Node类

public class LinkedListQueue <E>implements Queue<E>, Iterable<E>{Node<E> head=new Node<>(null,null);//头指针一直指向哨兵节点Node<E> tail=head;int size=0;int capacity=Integer.MAX_VALUE;{tail.next=head;}private static class Node<E>{E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}
}public LinkedListQueue(int capacity) {this.capacity = capacity;}public LinkedListQueue() {}

我们在这个类中将每次构造的队列对象的tail节点都指向head节点

接下来我们实现各个功能操作

代码如下

public 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;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;}
}


http://www.ppmy.cn/server/141198.html

相关文章

【ROS2】usb摄像头识别二维码

1、安装依赖 1)安装usb摄像头 ROS包: sudo apt install ros-humble-usb-cam2)安装二维码识别库 sudo apt install libzbar-dev3)安装opencv cv::Mat和sensor_msgs转换库 sudo apt install ros-humble-cv-bridge4)安装pydantic库 pip3 install pydantic==1.10.7注意版…

ImportError: cannot import name ‘packaging‘ from ‘pkg_resources‘ 的参考解决方法

文章目录 写在前面一、问题描述二、解决方法参考链接 写在前面 自己的测试环境&#xff1a; Ubuntu20.04 ROS-Noetic 一、问题描述 自己在通过 pip install 安装module时 &#xff08;使用的是 pip install mmcv&#xff09;遇到如下问题&#xff1a; ImportError: cannot …

rust字符串

Rust字符串 在Rust中&#xff0c;字符串(string)是一种非常重要的数据类型&#xff0c;用于表示文本数据。Rust中的字符串有两种类型&#xff1a;String和&str。 String类型是可变的、堆分配的字符串类型&#xff0c;可以动态地增加或删除字符。例如&#xff0c;下面创建了…

Vite与Vue Cli的区别与详解

它们的功能非常相似&#xff0c;都是提供基本项目脚手架和开发服务器的构建工具。 主要区别 Vite在开发环境下基于浏览器原生ES6 Modules提供功能支持&#xff0c;在生产环境下基于Rollup打包&#xff1b; Vue Cli不区分环境&#xff0c;都是基于Webpack。 在生产环境下&…

初识Electron 进程通信

概述 Electron chromium nodejs native API&#xff0c;也就是将node环境和浏览器环境整合到了一起&#xff0c;这样就构成了桌面端&#xff08;chromium负责渲染、node负责操作系统API等&#xff09; 流程模型 预加载脚本&#xff1a;运行在浏览器环境下&#xff0c;但是…

半导体制造技术导论(第二版)萧宏 第五章集成电路加热工艺答案

本章要求 1. 至少列出三种重要的加热工艺 水平式高温炉加热、垂直式高温炉加热&#xff08;即传统的管式炉加热&#xff09;、快速加热工艺RTP、激光镭射 退火LSA 2. 说明直立式和水平式炉管的基本系统&#xff0c;以及直立式炉管的优点 基本系统&#xff1a;控制系统…

VR的左右眼渲染方法

VR的左右眼视频渲染shader unity_StereoEyeIndex 结点可以判断当前渲染的时候左眼还是右眼&#xff0c;所以可以通过着色器来更根据当前眼睛使用不同的渲染方式达到左右眼渲染不同。 Shader "Unlit/VRVideoPlay" {Properties{_MainTex ("Texture", 2D) …

【Flume实操】实时监听 NetCat 端口和本地文件数据到 HDFS 案例分析

聚合&#xff1a;实时监听 NetCat 端口和本地文件数据到 HDFS 案例分析 案例需求&#xff1a;假设有一个生产场景&#xff0c;Flume1 在实时产生日志数据&#xff0c;日志类型为 flume.log。Flume2 在持续监控一个 netcat 端口的数据流。先需要将 Flume1、Flume2产生的数据采集…