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

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

什么是队列结构

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

分类：

顺序队列结构

链式队列结构

基本操作：

入队列

出队列

给出一些应用队列的场景

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

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

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

队列是先进先出的!

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

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

//链的数据结构

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 qTdiNUvoid 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 {

//链的数据结构

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)

qTdiNU rear=front;

//删除节点

p=null;

size--;

return x;

}

}

/http://**

* 队列长队

* @return

* @author WWX

*/

public int size(){

return size;

}

/**

* 判断队列是否为空

* @return

* @author WWX

*/

public Boolean isEmpty(){

return size==0;

}

}

另：我曾经看过一本javascript数据结构书，里面讲的浅显易懂，很适合前端搞js开发的让人理解的更为深入，在此给予推荐。

《数据结构与算法javaScript描述》

总结

以上就是本文关于java实现队列数据结构代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：

Java编程用两个栈实现队列代码分享

java编程实现优先队列的二叉堆代码分享

java编程队列数据结构代码示例

如有不足之处，欢迎留言指出。

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