java实现队列数据结构代码详解
作者:颜小雀 发布时间:2023-06-20 15:35:47
什么是队列结构
一种线性结构,具有特殊的运算法则【只能在一端(队头)删除,在另一端(队尾)插入】。
分类:
顺序队列结构
链式队列结构
基本操作:
入队列
出队列
给出一些应用队列的场景
1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点。
2):售票口的人买票的顺序的按照先来先买的顺序售票。
3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候。
队列是先进先出的!
我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node 作为内部类(作为节点用),它包含了泛型元素和下一个node节点的指向next(Node)。
在Linkqueue的里面设置队列头指针 front和队列尾指针rear,长度size=0;我们先设置一个构造器LinkQueue(),用来初始化这两个指针节点,当然,刚开始初始化的时候 这两个指针仅仅是一个节点而已,里面的data是空的,我们还让这两个指针相等。
//链的数据结构
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;
public LinkQueue(){
Node n=new Node(null,null);
n.next=null;
front=rear=n;
}
当我们向该队列添加元素的时候,就会生成一个新的节点,其data就是你要加的元素,(当添加一个节点时,该节点就是队尾指针指向的最后的节点,一直排在最后),所以队尾rear.next=newNode(“新创建的节点”).这是第一个节点,也是最后一个节点,所以front.next=newNode.然后我们再让rear=newNode(不断更新)。
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;这样头指针就指向了第二个元素(每一次调用的时候队列头指针指会发生变化)。
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(是否为空),就不在说了。(因为太简单了!)
具体源码如下:
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 WWX
*/
public void enqueue(T data){
//创建一个节点
Node s=new Node(data,null);
//将队尾指针指向新加入的节点,将s节点插入队尾
rear.next=s;
rear=s;
size++;
}
/**
* 队列出队算法
* @return
* @author WWX
*/
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;
}
}
另:我曾经看过一本JavaScript数据结构书,里面讲的浅显易懂,很适合前端搞js开发的让人理解的更为深入,在此给予推荐。
《数据结构与算法JavaScript描述》
如有不足之处,欢迎留言指出。
来源:https://www.cnblogs.com/coversky/p/6350086.html
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 一、ViewPageIndicator开源框架的基本用法 我们先得去Github上面下载这个库,下载地址:https://github.co
- /** * 冒泡排序估计是每本算法书籍都会提到的排序方法。 * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列。 * 第1趟
- 一、logback日志技术介绍Spring Boot中使用的日志技术为logback。其与Log4J都出自同一人,性能要优于Log4J,是L
- 1. 多行编辑先来体验一下从xml文件拷贝字段新建实体对象一般我们为了新建多表连接后映射的 ResultMap ,耗费不少时间,那么我们就来
- 实习一段时间了,一直想写点技术总结,但一直没找到合适的主题。刚好,最近版本中我负责的模块遇到了个线程相关问题(之前一直画界面,做点基础功能,
- 邮件发送 方法一:使用System.Web.Mail命名空间(此方法我测试没有成功过) #region 发送邮件:此方法失败 pr
- EntityWrapper的in用法EntityWrapper<UserLife> wrapper = new EntityWr
- 结构体有时候我们仅需要一个小的数据结构,类提供的功能多于我们需要的功能;考虑到性能原因,最好使用结构体。结构体是值类型,存储在栈中或存储为内
- 一、访问或添加request/session/application属性public String scope() throws Excep
- 在上一篇笔记 《SpringMVC实现图片上传》记录了将图片上传到本地的实现,在很多项目中都会有一台专门的文件服务器来保存文件的,这边记录下
- 本文以实例形式演示了C#虚方法的声明与使用。实例内容主要包括:演示虚方法的声明和使用,定义虚方法进而求几何面积,用虚方法求原始图形的面积、正
- 本文的控制台项目是根据SuperSocket官方Telnet示例代码进行调试的,官方示例代码:Telnet示例。开始我的第一个Telnet控
- Android上使调用OpenCV 2.4.10 实现二维码区域定位(Z-xing 码),该文章主要用于笔者自己学习中的总结,暂贴出代码部分
- 概念Java中的集合就是一种容器,可以容纳不同种类的数据,这些容纳是建立在未知的基础上。优点1.可以动态保存任意多个对象,使用比较方便。2.
- 背景最近让我做一个大数据的系统,分析了一下,麻烦的地方就是多数据源切换抽取数据。考虑到可以跨服务器跨数据库抽数,再整理数据,就配置了这个动态
- 这篇文章主要介绍了基于Java检查IPv6地址的合法性,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 利用 Spring 工厂加载机制,实例化 ApplicationListener 实现类,并排序对象集合创建应用事件 * 创建类实现接口Ap
- SpringBoot默认加载的是application.yml文件,所以想要引入其他配置的yml文件,就要在application.yml中
- 1.本系统和现在有的考试系统有以下几种优势:a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已
- 访问登记属性 android.permission.ACCESS_CHECKIN_PROPERTIES ,读取或写入登记check-in数据