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

时间:2021-08-06 00:29:40

什么是队列结构

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

分类:

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

基本操作:

入队列
出队列 

给出一些应用队列的场景

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

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

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

队列是先进先出的! 

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//链的数据结构
 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;
?
1
2
3
4
5
public LinkQueue(){
    Node n=new Node(null,null);
    n.next=null;
    front=rear=n;
}

当我们向该队列添加元素的时候,就会生成一个新的节点,其data就是你要加的元素,(当添加一个节点时,该节点就是队尾指针指向的最后的节点,一直排在最后),所以队尾rear.next=newNode(“新创建的节点”).这是第一个节点,也是最后一个节点,所以front.next=newNode.然后我们再让rear=newNode(不断更新)。

?
1
2
3
4
5
6
7
8
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;这样头指针就指向了第二个元素(每一次调用的时候队列头指针指会发生变化)。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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(是否为空),就不在说了。(因为太简单了!)

具体源码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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开发的让人理解的更为深入,在此给予推荐。如有不足之处,欢迎留言指出。

原文链接:https://www.cnblogs.com/coversky/p/6350086.html