java队列实现方法(顺序队列,链式队列,循环队列)

2023-09-19 06:00:05 50
双向顺序队列ArrayDeque和双向链式队列LinkedList，JDK已经包含，在此略。ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。PriorityQueue优先队列也在JDK。
1.顺序队列的实现
packagelang;
importjava.io.Serializable;
importjava.util.Arrays;
/**
*@ClassName:ArrayQueue
*@Description:顺序队列
*@date2014年1月20日下午3:46:19
*@param
*/
publicclassArrayQueueimplementsSerializable{
/**
*@FieldsserialVersionUID:TODO
*/
privatestaticfinallongserialVersionUID=7333344126529379197L;
privateintDEFAULT_SIZE=10;
privateintcapacity;//保存数组的长度
privateObject[]elementData;//定义一个数组用于保存顺序队列的元素
privateintfront=0;//队头
privateintrear=0;//队尾
//以默认数组长度创建空顺序队列
publicArrayQueue(){
capacity=DEFAULT_SIZE;
elementData=newObject[capacity];
}
//以一个初始化元素来创建顺序队列
publicArrayQueue(Telement){
this();
elementData[0]=element;
rear++;
}

publicArrayQueue(intinitSize){
elementData=newObject[initSize];
}
/**
*以指定长度的数组来创建顺序队列
*@paramelement指定顺序队列中第一个元素
*@paraminitSize指定顺序队列底层数组的长度
*/
publicArrayQueue(Telement,intinitSize){
this.capacity=initSize;
elementData=newObject[capacity];
elementData[0]=element;
rear++;
}
/**
*@Title:size
*@Description:获取顺序队列的大小
*@return
*/
publicintsize(){
returnrear-front;
}
/**
*@Title:offer
*@Description:入队
*@paramelement
*/
publicvoidoffer(Telement){
ensureCapacity(rear+1);
elementData[rear++]=element;
}

privatevoidensureCapacity(intminCapacity){
//如果数组的原有长度小于目前所需的长度
intoldCapacity=elementData.length;
if(minCapacity>oldCapacity){
intnewCapacity=(oldCapacity*3)/2+1;
if(newCapacity
2.链式队列的实现
packagelang;
importjava.io.Serializable;
/**
*@ClassName:LinkQueue
*@Description:链式队列
*@date2014年1月21日下午3:24:38
*@param
*/
publicclassLinkQueueimplementsSerializable{
/**
*@FieldsserialVersionUID:TODO
*/
privatestaticfinallongserialVersionUID=-6726728595616312615L;
//定义一个内部类Node，Node实例代表链队列的节点。
privateclassNode{

privateTdata;//保存节点的数据

privateNodenext;//指向下个节点的引用
//无参数的构造器
publicNode(){
}
//初始化全部属性的构造器
publicNode(Tdata,Nodenext){
this.data=data;
this.next=next;
}
}

privateNodefront;//保存该链队列的头节点

privateNoderear;//保存该链队列的尾节点
privateintsize;//保存该链队列中已包含的节点数
/**
*Title:LinkQueue
*Description:创建空链队列
*/
publicLinkQueue(){
//空链队列，front和rear都是null
front=null;
rear=null;
}
/**
*Title:LinkQueue
*Description:以指定数据元素来创建链队列，该链队列只有一个元素
*/
publicLinkQueue(Telement){
front=newNode(element,null);
//只有一个节点，front、rear都指向该节点
rear=front;
size++;
}
/**
*@Title:size
*@Description:获取顺序队列的大小
*@return
*/
publicintsize(){
returnsize;
}
/**
*@Title:offer
*@Description:入队
*@paramelement
*/
publicvoidoffer(Telement){
//如果该链队列还是空链队列
if(front==null){
front=newNode(element,null);
rear=front;//只有一个节点，front、rear都指向该节点
}else{
NodenewNode=newNode(element,null);//创建新节点
rear.next=newNode;//让尾节点的next指向新增的节点
rear=newNode;//以新节点作为新的尾节点
}
size++;
}
/**
*@Title:poll
*@Description:出队
*@return
*/
publicTpoll(){
NodeoldFront=front;
front=front.next;
oldFront.next=null;
size--;
returnoldFront.data;
}
/**
*@Title:peek
*@Description:返回队列顶元素，但不删除队列顶元素
*@return
*/
publicTpeek(){
returnrear.data;
}
/**
*@Title:isEmpty
*@Description:判断顺序队列是否为空队列
*@return
*/
publicbooleanisEmpty(){
returnsize==0;
}
/**
*@Title:clear
*@Description:清空顺序队列
*/
publicvoidclear(){
//将front、rear两个节点赋为null
front=null;
rear=null;
size=0;
}
publicStringtoString(){
//链队列为空链队列时
if(isEmpty()){
return"[]";
}else{
StringBuildersb=newStringBuilder("[");
for(Nodecurrent=front;current!=null;current=current.next){
sb.append(current.data.toString()+",");
}
intlen=sb.length();
returnsb.delete(len-2,len).append("]").toString();
}
}
publicstaticvoidmain(String[]args){
LinkQueuequeue=newLinkQueue("aaaa");
//添加两个元素
queue.offer("bbbb");
queue.offer("cccc");
System.out.println(queue);
//删除一个元素后
queue.poll();
System.out.println("删除一个元素后的队列："+queue);
//再次添加一个元素
queue.offer("dddd");
System.out.println("再次添加元素后的队列："+queue);
//删除一个元素后，队列可以再多加一个元素
queue.poll();
//再次加入一个元素
queue.offer("eeee");
System.out.println(queue);
}
}

3.循环队列的实现
packagelang;
importjava.io.Serializable;
importjava.util.Arrays;
/**
*@ClassName:LoopQueue
*@Description:循环队列
*@date2014年1月20日下午3:47:14
*/
publicclassLoopQueueimplementsSerializable{
/**
*@FieldsserialVersionUID:TODO
*/
privatestaticfinallongserialVersionUID=-3670496550272478781L;
privateintDEFAULT_SIZE=10;
privateintcapacity;//保存数组的长度
privateObject[]elementData;//定义一个数组用于保存循环队列的元素
privateintfront=0;//队头
privateintrear=0;//队尾
//以默认数组长度创建空循环队列
publicLoopQueue(){
capacity=DEFAULT_SIZE;
elementData=newObject[capacity];
}
//以一个初始化元素来创建循环队列
publicLoopQueue(Telement){
this();
elementData[0]=element;
rear++;
}
/**
*以指定长度的数组来创建循环队列
*@paramelement指定循环队列中第一个元素
*@paraminitSize指定循环队列底层数组的长度
*/
publicLoopQueue(Telement,intinitSize){
this.capacity=initSize;
elementData=newObject[capacity];
elementData[0]=element;
rear++;
}
//获取循环队列的大小
publicintsize(){
if(isEmpty()){
return0;
}
returnrear>front?rear-front:capacity-(front-rear);
}
//插入队列
publicvoidadd(Telement){
if(rear==front&&elementData[front]!=null){
thrownewIndexOutOfBoundsException("队列已满的异常");
}
elementData[rear++]=element;
//如果rear已经到头，那就转头
rear=rear==capacity?0:rear;
}
//移除队列
publicTremove(){
if(isEmpty()){
thrownewIndexOutOfBoundsException("空队列异常");
}
//保留队列的rear端的元素的值
ToldValue=(T)elementData[front];
//释放队列的rear端的元素
elementData[front++]=null;
//如果front已经到头，那就转头
front=front==capacity?0:front;
returnoldValue;
}
//返回队列顶元素，但不删除队列顶元素
publicTelement(){
if(isEmpty()){
thrownewIndexOutOfBoundsException("空队列异常");
}
return(T)elementData[front];
}
//判断循环队列是否为空队列
publicbooleanisEmpty(){
//rear==front且rear处的元素为null
returnrear==front&&elementData[rear]==null;
}
//清空循环队列
publicvoidclear(){
//将底层数组所有元素赋为null
Arrays.fill(elementData,null);
front=0;
rear=0;
}
publicStringtoString(){
if(isEmpty()){
return"[]";
}else{
//如果front=rear，有效元素为front->capacity之间、0->front之间的
else{
StringBuildersb=newStringBuilder("[");
for(inti=front;iqueue=newLoopQueue("aaaa",3);
//添加两个元素
queue.add("bbbb");
queue.add("cccc");
//此时队列已满
System.out.println(queue);
//删除一个元素后，队列可以再多加一个元素
queue.remove();
System.out.println("删除一个元素后的队列："+queue);
//再次添加一个元素，此时队列又满
queue.add("dddd");
System.out.println(queue);
System.out.println("队列满时的长度："+queue.size());
//删除一个元素后，队列可以再多加一个元素
queue.remove();
//再次加入一个元素，此时队列又满
queue.add("eeee");
System.out.println(queue);
}
}

以上这篇java队列实现方法(顺序队列,链式队列,循环队列)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。
java队列实现方法(顺序队列,链式队列,循环队列)

热门推荐

随机推荐
