Java自定义实现链队列详解

一、写在前面

        数据结构中的队列应该是比较熟悉的了,就是先进先出,因为有序故得名队列,就如同排队嘛,在对尾插入新的节点,在对首删除节点.jdk集合框架也是提供也一个queue的接口.这个接口代表一个队列.顺序队列:arrayblockingqueue,linkedblockingqueue.(上面两种是足色队列)还有一种是concurentlinkedqueue。
底层的实现由数组合链表两种的,数组的实现会有个弊端的,会造成假满的现象,开始的时候,队列为空的时候,对首引用变量个对尾的引用变量都为null,随着删除队列的元素,就会发生front+1,rear等于底层数组的容量了.在顺序的存储结构中,front总是保存这着队列中即将出队列的元素的索引,rear总是保存着即将进入队列的元素的索引.队列中的元素的个数就是rear-front的.在顺序的队列中,底层是数组,所以保存 的数据元素是不会改变的,改变的只有rear和front这两个引用变量.
        这里采用链式存储可以有效的利用空间的,就是引用变量要占用额外的空间的.

队列的常用的操作:

             1:初始化
             2:返回队列的长度
             3:添加元素
             4:删除元素
             5:访问对首的元素
             6:访问队列的对尾的元素
             7:判断队列是否为空
             8:清空队列

二、自定义的实现

源码展示的比较清楚,就不用再多做介绍

public class linkedqueue<t>{
//自定义链队列--采用非静态内部类来表示链队列的数据节点
private class node{
//表示链队列的数据节点 
private t data;
//指向下一个节点的引用
private node next;
 @suppresswarnings("unused")
 public node(){
 
}
public node(t data,node next){
 this.data=data;
 this.next=next;
 }
}
//定义链队列的对首和对尾的引用
 private node front;
 private node rear;
 //定义链栈的大小
private int size;
 //创建一个空的链对列
public linkedqueue(){
 front=null;
 rear=null;
}
//以确定的元素来创建一个链对列,只有一个节点的
public linkedqueue(t element){
front=new node(element,null);
//指向同一个元素
rear=front;
size++;
}
//返回链队列的大小
public int length(){
return size;
}
//返回链队列得对首的元素,不删除对首的元素
public t elementfront(){
if(!empty()){
 return front.data;
}else{
 return null; 
 
}
}
//访问队列的最后一个元素
public t elementrear(){
if(!empty()){
 return rear.data;
 
}else{
 return null; 
} 
}
//返回当前的链对队列是否为空
public boolean empty(){
 return size==0;
 }
//清空一个链队列
public void clear(){
 front=null;
 rear=null;
 size=0;
}
//插入链队列一个节点--对尾
public void add(t element){
 //如果链对列为空,就新建一个节点
 if(front==null){
 rear=new node(element,null);
 front=rear;
 }else{
 //动态创建新节点
 node newrear=new node(element,null);
 rear.next=newrear;
 rear=newrear; 
}
size++;
}
//删除链队列一个节点,返回删除后的节点
public t remove(){
   node oldfront=front;
   front=front.next;
   oldfront.next=null;
   size--;
   return oldfront.data;
}
//返回队列
public string tostring(){
 //如果链队列为空链队列是
 if(empty()){
 return "[]";
 }else{
 stringbuilder sbuilder=new stringbuilder("[");
 for(node current=front;current!=null;current=current.next){
 sbuilder.append(current.data.tostring()+",");
}
 int len=sbuilder.length();
return sbuilder.delete(len-1, len).append("]").tostring();
}
}
public static void main(string[] args) {
 linkedqueue<string> lqueue=new linkedqueue<string>();
 lqueue.add("aaa");
 lqueue.add("bbb");
 lqueue.add("ccc");
 lqueue.add("ddd");
system.out.println("返回队列的头结点的数值:"+lqueue.elementfront());
system.out.println("返回队列的尾节点的数值:"+lqueue.elementrear());
system.out.println(lqueue.length());
system.out.println(lqueue);
}
}  

运行结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。