【代码】线性表之队列

发表于 更新于 阅读次数：

前言

线性表之队列的Java版实现

源代码

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
package com;

public class Queue<T> {

    public Node head;
    public Integer queueLength;

    private class Node {
        public T data;
        public Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Queue() {
        head = new Node(null, null);
        queueLength = 0;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return queueLength==0;
    }

    /**
     * 获取队列中所有元素的个数
     * @return
     */
    public int size() {
        return queueLength;
    }

    public void enQueue(T t) {
        // 创建一个新结点
        Node node = new Node(t, null);
        if (!isEmpty()) {
            // 把新结点的写一个结点设置为头结点的下一个结点
            node.next = head.next;
        }
        // 把头结点的下一个结点设置为新结点
        head.next = node;
        // 长度自增
        queueLength++;
    }

    public T deQueue() {
        // 找到最后一个结点的上一个结点
        Node n = head;
        for (int i = 0; i < queueLength-1; i++) {
            n = n.next;
        }
        // 记录最后一个结点
        Node nLast = n.next;
        // 把最后一个结点的上一个结点的下一个结点设置为空
        n.next = null;
        // 长度自减
        queueLength--;
        return nLast.data;
    }

    public String toString() {
        String str = "";
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            str += n.data + " ";
        }
        return str;
    }

}

源代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package com;

import java.util.Iterator;
import java.util.Objects;
import java.util.function.Consumer;

public class Queue<T> implements Iterable<T> {

    public Node head;
    public Integer queueLength;
    public Node last;

    @Override
    public Iterator<T> iterator() {
        return null;
    }

    @Override
    public void forEach(Consumer action) {
        Objects.requireNonNull(action);
        Node n = head;
        for (int i = 0; i < queueLength; i++) {
            n = n.next;
            action.accept(n.data);
        }
    }


    private class Node {
        public T data;
        public Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Queue() {
        this.head = new Node(null, null);
        this.last = null;
        this.queueLength = 0;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return queueLength==0;
    }

    /**
     * 获取队列中所有元素的个数
     * @return
     */
    public int size() {
        return queueLength;
    }

    // 入队列
    public void enQueue(T t) {
        if (last==null) {
            last = new Node(t, null);
            head.next = last;
        } else {
            Node node = new Node(t, null);
            node.next = head.next;
            head.next = node;
        }
        // 长度自增
        queueLength++;
    }

    // 出队列
    public T deQueue() {
        if (isEmpty()) {
            return null;
        }
        Node node = head;
        Node n = last;
        while (true) {
            if (node.next!=last) {
                node = node.next;
            } else {
                last = node;
                break;
            }
        }
        // 长度自减
        queueLength--;
        if (isEmpty()) {
            last = null;
        }
        return n.data;
    }

    public String toString() {
        String str = "";
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            str += n.data + " ";
        }
        return str;
    }

}

完成

参考文献

哔哩哔哩——黑马程序员