Java自定义实现链队列详解

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{

//自定义链队列--采用非静态内部类来表示链队列的数据节点

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 dyuSmbNode 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 lQueue=new LinkedQueue();

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);

}

}

运行结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。