java实现队列数据结构代码详解

2024-07-13 10:14:01

字体：大中小

来源：转载

供稿：网友

什么是队列结构

一种线性结构，具有特殊的运算法则【只能在一端（队头）删除，在另一端（队尾）插入】。

分类：

顺序队列结构
链式队列结构

基本操作：

入队列
出队列　

给出一些应用队列的场景

　　1):当作业被送到打印机的时候，就可以按到达的顺序排起来，因此每一份作业是队列的节点。

　　2):售票口的人买票的顺序的按照先来先买的顺序售票。

　　3):当所有的终端被占用，由于资源有限，来访请求需要放在一个队列中等候。

队列是先进先出的!　

我们设置一个叫做LinkQueue<T>的泛型集合类，该类里面有 Node 作为内部类（作为节点用），它包含了泛型元素和下一个node节点的指向next（Node）。

在Linkqueue的里面设置队列头指针 front和队列尾指针rear，长度size=0；我们先设置一个构造器LinkQueue()，用来初始化这两个指针节点，当然，刚开始初始化的时候这两个指针仅仅是一个节点而已，里面的data是空的，我们还让这两个指针相等。

java/210302.html">java;">//链的数据结构  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开发的让人理解的更为深入，在此给予推荐。

总结

以上就是本文关于java实现队列数据结构代码详解的全部内容，希望对大家有所帮助。

注：相关教程知识阅读请移步到JAVA教程频道。

上一篇：java 文件和byte互转的实例

下一篇：springboot 中文件上传下载实例代码