java实现队列数据结构代码详解

简介: 本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。

java实现队列数据结构代码详解

 

java实现队列数据结构代码详解,简单介绍了队列结构以应用场景,涉及详细实现代码。

什么是队列结构

一种线性结构,具有特殊的运算法则【只能在一端(队头)删除,在另一端(队尾)插入】。

  • 队列是一种特殊的线性表
  • 它只允许在表的前端(队头)进行删除操作
  • 在表的后端(队尾)进行插入操作
  • 队列是一个有序表(可以用数组或链表实现)
  • 队列先进先出
  • 队列开辟的是一块连续的空间

分类:

顺序队列结构

链式队列结构\

顺序队列中的溢出现象:

  • 真溢出: 当队列满时,做进栈运算产生空间溢出的现象。
  • 假上溢: 由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。

循环队列

在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0,可用取余运算rear%MaxSizefront%MaxSize来实现。这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列

给出一些应用队列的场景

  1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点。

  2):售票口的人买票的顺序的按照先来先买的顺序售票。

  3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候。

队列是先进先出的!

我们设置一个叫做LinkQueue的泛型集合类,该类里面有 Node 作为内部类(作为节点用),它包含了泛型元素和下一个node节点的指向next(Node)。

在Linkqueue的里面设置队列头指针 front和队列尾指针rear,长度size=0;我们先设置一个构造器LinkQueue(),用来初始化这两个指针节点,当然,刚开始初始化的时候 这两个指针仅仅是一个节点而已,里面的data是空的,我们还让这两个指针相等。

java

代码解读

复制代码

    //链的数据结构 
 private class Node{ 
 public T data; 
 public Node next; 
 //无参构造函数 
 public Node(){} 
  
 public Node(T data,Node next){ 
  this.data=data; 
  this.next=next; 
 } 
 } 
 //队列头指针 
 private Node front; 
 //队列尾指针 
 private Node rear;

java

代码解读

复制代码

   public LinkQueue(){
	Node n=new Node(null,null);
	n.next=null;
	front=rear=n;
} 

当我们向该队列添加元素的时候,就会生成一个新的节点,其data就是你要加的元素,(当添加一个节点时,该节点就是队尾指针指向的最后的节点,一直排在最后),所以队尾rear.next=newNode(“新创建的节点”).这是第一个节点,也是最后一个节点,所以front.next=newNode.然后我们再让rear=newNode(不断更新)。

java

代码解读

复制代码

   public void enqueue(T data){ 
 //创建一个节点 
 Node s=new Node(data,null); 
 //将队尾指针指向新加入的节点,将s节点插入队尾 
 rear.next=s; 
 rear=s; 
 size++; 
 } 

当队列出队的时候,还记得我们有一个Node是front.next=newNode 吗?这就是第一个节点。先暂且把它叫做p,所以p.next=第二个节点,这时我们再把front.next=p.next;这样头指针就指向了第二个元素(每一次调用的时候队列头指针指会发生变化)。

java

代码解读

复制代码

    public T dequeue(){ 
 if(rear==front){ 
  try { 
  throw new Exception("堆栈为空"); 
  } catch (Exception e) { 
  e.printStackTrace(); 
  } 
  return null; 
 }else{ 
  //暂存队头元素 
  Node p=front.next; 
  T x=p.data; 
  //将队头元素所在节点摘链 
  front.next=p.next; 
  //判断出队列长度是否为1 
  if(p.next==null) 
  rear=front; 
  //删除节点 
  p=null; 
  size--; 
  return x; 
 } 
 }

到此为止,队列的核心操作就完毕了,剩下的比如说size(长度),isEmpty(是否为空),就不在说了。 具体源码如下:

java

代码解读

复制代码

   public class LinkQueue<T> {
	//链的数据结构 
	private class Node{
		public T data;
		public Node next;
		//无参构造函数 
		public Node(){
		}
		public Node(T data,Node next){
			this.data=data;
			this.next=next;
		}
	}
	//队列头指针 
	private Node front;
	//队列尾指针 
	private Node rear;
	//队列长度 
	private int size=0;
	public LinkQueue(){
		Node n=new Node(null,null);
		n.next=null;
		front=rear=n;
	}
	/** 
 * 队列入队算法 
 * @param data 
 * @author xuda
 */
	public void enqueue(T data){
		//创建一个节点 
		Node s=new Node(data,null);
		//将队尾指针指向新加入的节点,将s节点插入队尾 
		rear.next=s;
		rear=s;
		size++;
	}
	/** 
 * 队列出队算法 
 * @return 
 * @author xuda
 */
	public T dequeue(){
		if(rear==front){
			try {
				throw new Exception("堆栈为空");
			}
			catch (Exception e) {
				e.printStackTrace();
			}
			return null;
		} else{
			//暂存队头元素 
			Node p=front.next;
			T x=p.data;
			//将队头元素所在节点摘链 
			front.next=p.next;
			//判断出队列长度是否为1 
			if(p.next==null) 
			  rear=front;
			//删除节点 
			p=null;
			size--;
			return x;
		}
	}
	/** 
 * 队列长队 
 * @return 
 * @author WWX 
 */
	public int size(){
		return size;
	}
	/** 
 * 判断队列是否为空 
 * @return 
 * @author WWX 
 */
	public Boolean isEmpty(){
		return size==0;
	}
}

总结

以上就是本文关于java实现队列数据结构代码详解的全部内


转载来源:https://juejin.cn/post/7129108038224445448

目录
打赏
0
1
1
0
179
分享
相关文章
快手小红书抖音留痕工具,自动留痕插件工具,java代码开源
这个框架包含三个核心模块:主操作类处理点赞评论、配置管理类和代理管理类。使用时需要配合
tiktok群控脚本,养号关注私信点赞脚本插件,java代码分享
这个代码模拟了一个社交机器人的基本行为模式,包括登录、关注、点赞、私信等操作。请注意
Java异常处理:写出更健壮的代码
Java异常处理:写出更健壮的代码
Java 面试资料中相关代码使用方法与组件封装方法解析
这是一份详尽的Java面试资料代码指南,涵盖使用方法与组件封装技巧。内容包括环境准备(JDK 8+、Maven/Gradle)、核心类示例(问题管理、学习进度跟踪)、Web应用部署(Spring Boot、前端框架)、单元测试及API封装。通过问题库管理、数据访问组件、学习进度服务和REST接口等模块化设计,帮助开发者高效组织与复用功能,同时支持扩展如用户认证、AI推荐等功能。适用于Java核心技术学习与面试备考,提升编程与设计能力。资源链接:[点此下载](https://pan.quark.cn/s/14fcf913bae6)。
74 6
Java 面试资料中相关代码使用方法与组件封装方法解析
Java 期末考试救急必备涵盖绝大多数核心考点及五大类经典代码助你过关
本文为Java期末考试复习指南,涵盖基础语法、面向对象编程、异常处理、文件操作、数据库连接五大核心考点,提供详细解析与实用代码示例,助力快速掌握重点,高效备考,轻松应对考试。
32 0
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
130 3
基于Java 17 + Spring Boot 3.2 + Flink 1.18的智慧实验室管理系统核心代码
这是一套基于Java 17、Spring Boot 3.2和Flink 1.18开发的智慧实验室管理系统核心代码。系统涵盖多协议设备接入(支持OPC UA、MQTT等12种工业协议)、实时异常检测(Flink流处理引擎实现设备状态监控)、强化学习调度(Q-Learning算法优化资源分配)、三维可视化(JavaFX与WebGL渲染实验室空间)、微服务架构(Spring Cloud构建分布式体系)及数据湖建设(Spark构建实验室数据仓库)。实际应用中,该系统显著提升了设备调度效率(响应时间从46分钟降至9秒)、设备利用率(从41%提升至89%),并大幅减少实验准备时间和维护成本。
126 0
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
【Java 数据结构及算法实战】系列 014:Java队列08——数组实现的双端队列ArrayDeque
【Java 数据结构及算法实战】系列 014:Java队列08——数组实现的双端队列ArrayDeque
213 0
【Java 数据结构及算法实战】系列 014:Java队列08——数组实现的双端队列ArrayDeque
【Java数据结构及算法实战】系列012:Java队列06——数组实现的优先级阻塞队列PriorityBlockingQueue
【Java数据结构及算法实战】系列012:Java队列06——数组实现的优先级阻塞队列PriorityBlockingQueue
180 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问