java队列--数据结构

news/2024/12/28 3:53:41 标签: java, 数据结构, 开发语言, eclipse, 学习

文章目录

  • 前言
  • 本文源代码网址:https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue
  • 队列的性质
  • 数组队列
    • 成员变量
    • 方法
  • 链表栈
    • 成员变量
    • 方法
  • 总结


前言

顺序表和链表两种存储方式实现数据结构–队列。


javatreemasterdataStructuresrccomnjuptqueue_12">本文源代码网址:https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue

https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue


队列的性质

先进先出。如果一个单向行驶的隧道,先进隧道的先出去,后面一个接着一个排队,顺序不可打乱。

数组队列

成员变量

1.一个数组,存储数据
2.一个size,表示队列长度
3.head和tail,队列不像栈只在一端进出数据,所以要定义head和tail两个标志一进一出,我们以头出尾进为例。

方法

用数组实现队列,和数组实现栈一样,两种构造方法。


数据进入队列:
不能用栈的push,约定俗成push和pop时栈的方法,队列用in和out。

正常情况下:只需要在tail+1的位置存入新数据,但是由于head方会出数据,有多余的空间,还能进数据,所以tail = (tail+1)%this.values.length 。用取模使得数组循环起来,剩余的空间也能循环利用。值得注意的是,如果是进第一个数据,head的值要变为tail。

java">this.tail = (this.tail+1)%this.values.length;
this.values[this.tail] = num;
this.size++;
if(this.size==1) this.head = this.tail;

也有可能遇到整个数组都被用完的情况,这个时候我们需要扩容。

在搬移数据时和栈不同,栈搬数据只需要将短数组数据一个一个搬入长数组,下标一样。但是队列进进出出,下标不知道是多少。干脆从head开始一个一个搬进长数组,长数组从下标为0开始。因为满了才会扩容,所以循环次数为 this.values.length。短数组的下标仍然要+1取模,循环把数组前前后后的数组都读完。

java">public void capacityIncrease()
{
	T temp[] = (T[])new Object[(this.values.length+1)*2];
	int j=this.head;
	for(int i=0;i<this.values.length;i++)
	{
		temp[i] = this.values[j];
		j = (j+1)%this.size;
	}
	this.head = 0;
	this.tail = this.size-1;
	values = temp;
	System.out.println("capacity increased,size="+this.size);
}

最后头置0,尾时this.size-1。还要记得把temp临时数组赋给this.values。


数据出队列out
先判断队列是否为空,size是否为0。若为0,返回false,出数据失败。

然后head+1,仍然要取模,循环起来。this.size–。和进数据对应的,当this.size==0时,this.tail也要变为this.tail一样的值。因为最后一个数据tail和head肯定是一样的,out之后,head往前走,但是tail不动,tail在head的前面去了。如果再进数据,倒也没问题,但是如果其他地方要用 tail 和 head ,可能会出现奇怪的问题。所以能避免尽量避免。

链表栈

成员变量

仅需头结点,尾结点,size可有可无,如果有,有需要直接返回size;没有,有需要从头到尾遍历一遍,有多少个结点,就有多大的size。

头进尾出,还是头出尾进?

头插头删都是比较好处理的,关键是尾部。尾插也很容易,尾删就难了。先要遍历一遍找到尾的前一个结点,再把前一个结点的next变为null。所以尾进头出比较简便。

方法

无需自写构造函数。

in 进数据:尾插
注意第一个数据进入时,头节点也要指向第一个数据。

out 出数据:头删
删完最后一个数据时,head会变成空,但是tail仍然指向最后一个数据。再重新in新数据,使用起来没有问题。但是最好在删完数据时把tail置空,让垃圾回收器尽快把不用的空间回收了。

java">public boolean out()
{
	if(this.head == null) 
	{
		System.out.println("Out failed");
		return false;
	}	
	this.head = this.head.next;
	this.size--;
	if(this.head == null) this.tail = null;
	return true;
}

总结

顺序存储和链式存储在实现队列时优劣明显,链式比数组方便很多。不过数组实现队列运用的循环数组的思想比较有趣,和C语言专栏的密码专函小练习类似。


http://www.niftyadmin.cn/n/5802322.html

相关文章

微信V3支付报错 平台证书及平台证书序列号

1.平台证书及平台证书序列号设置错误报错&#xff1a; 错误1&#xff1a; Verify the response’s data with: timestamp1735184656, noncea5806b8cabc923299f8db1a174f3a4d0, signatureFZ5FgD/jtt4J99GKssKWKA/0buBSOAbWcu6H52l2UqqaJKvrsNxvodB569ZFz5G3fbassOQcSh5BFq6hvE…

D类音频应用EMI管理

1、前言 对于EMI&#xff0c;首先需要理解天线。频率和波长之间的关系&#xff0c;如下图所示。   作为有效天线所需的最短长度是λ/4。在空气中&#xff0c;介电常数是1&#xff0c;但是在FR4或玻璃环氧PCB的情况下&#xff0c;介电常数大约4.8。这种效应会导致信号在FR4材…

企业架构学习笔记-数字化转型

1. 企业数字化发展阶段 案例1.业务部门“点菜”&#xff0c;IT部门叫苦 随着企业信息化进程的不断推进&#xff0c;IT部门的角色和面临的挑战也在发生显著变化。在信息化建设的初级阶段&#xff0c;确实存在IT部门需要积极引导和说服业务部门重视信息技术价值的情况。当时&am…

【HarmonyOS】鸿蒙将资源文件夹Resource-RawFile下的文件存放到沙箱目录下

【HarmonyOS】鸿蒙将资源文件夹Resource-RawFile下的文件存放到沙箱目录下 一、问题背景 应用开发中&#xff0c;我们经常会遇到一些文件原先是放在资源文件夹 rawfile下&#xff0c;但是逻辑处理时&#xff0c;需要转移到本地沙箱才能操作。这种情况下&#xff0c;就需要将将…

【漏洞复现】灵当CRM datapdf.php 任意文件读取漏洞

免责声明 请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,作者不为此承担任何责任。工具来自网络,安全性自测,如有侵权请联系删除。本次测试仅供学习使用,如若非法他用,与平台和本文作…

【Git】—— 使用git操作远程仓库(gitee)

目录 一、远程仓库常用命令 1、从远程仓库克隆项目 2、查看关联的远程仓库 3、添加关联的远程仓库 4、移除关联的远程仓库 5、将本地仓库推送到远程仓库 6、从远程仓库拉取项目 二、分支命令 1、查询分支 2、创建分支 3、切换分支 4、推送到远程分支 5、合并分支 …

HTTP/2与HTTP1.X的对比及升级指南

文章目录 前言HTTP协议概述HTTP/1.xHTTP/2详解1. 二进制分帧层&#xff08;Binary Framing Layer&#xff09;2. 多路复用&#xff08;Multiplexing&#xff09;3. 头部压缩&#xff08;Header Compression&#xff09;4. 服务器推送&#xff08;Server Push&#xff09;5. 流优…

解决Springboot整合Shiro自定义SessionDAO+Redis管理会话,登录后不跳转首页

解决Springboot整合Shiro自定义SessionDAORedis管理会话&#xff0c;登录后不跳转首页 问题发现问题解决 问题发现 在Shiro框架中&#xff0c;SessionDAO的默认实现是MemorySessionDAO。它内部维护了一个ConcurrentMap来保存session数据&#xff0c;即将session数据缓存在内存…