Java队列实现

| ， | | | 3k

队列简单介绍

队列是一种常用的数据结构之一，与之前的栈类似，不过队列是“先进先出”。队列有队头（front）和队尾（rear），数据从队尾进入队列，从队头出队列，队头（front）指向队列的第一个数据，队尾（rear）指向队列中的最后一个数据。

队列实现

队列有很多种，这里只是介绍最基本的实现，采用链式存储，也就是链式队列，与之前的链表存储形式一样，通过结点对象描述一个数据，结点对象包含具体数据和下一个结点的引用。

队列有两个重要的概念，一个叫队头，一个叫队尾，队头指向的是第一个元素，而队尾指向的是最后一个元素。队列跟栈一样也是访问受限制的，所以队列也只有两个主要的操作：入队(enqueue)操作 和 出队(dequeue)操作 。入队操作就是将一个元素添加到队尾，出队操作就是从队头取出一个元素。

队列的底层实现可以用数组和链表，基于数组实现的队列叫作顺序队列，基于链表实现的队列叫作链式队列，下面我们分别用数组和链表来简单的实现这两种队列。

基于数组的队列

不管使用那种方式来实现队列，都需要定义两个指针分别指向队头和队尾，本文中我们用head指向队头，tail指向队尾，后面的示例中这将默认使用这个，有特殊的地方我会进行说明，先来看看顺序队列的入队、出队操作。

图中可以看出，入队时，队尾往后移动，队头保持不变，出队是队头往后移动，队尾保持不变。入队、出队操作的逻辑都比较简单，可能你有疑问的地方是：出队时为什么队头要往后移动而不是一直指向数组下标为0的位置？ 为什么呢？如果我们保持队头一直指向数组下标为0的位置，那每次出队操作后，后面的数据都需要往前挪一位，换句话说每次出队操作都需要进行数据迁移，而数据迁移的代价比较大，每次数据迁移的时间复杂度为O(n)，这样会极大的影响队列的使用性能。如果我们出队时，队头往后移动一位，这样我们就避免每次出队都进行数据迁移，我们只需要在只有在tail等于数组大小且head不等于0时，进行一次数据迁移，将已经出队留下的空间继续供入队时使用。下图是数据迁移的过程：

数据迁移时，从head位置开始的数据都需要往前移动head位，这样就把出队后的空间腾出来，供后续入队操作使用。

基于数组的队列实现代码：

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
/**
 * 基于数组的队列
 */
public class ArrayQueue {

    // 存放数据的数组
    private String[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;
    // 最后一个节点
    private int tail = 0;

    // 构造函数
    public ArrayQueue(int size){
        this.size = size;
        items = new String[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        // 如果最后一个节点等于容器大小，说明队列满了
        /**
         * 判断队列满了的条件，tail = size,head = 0,
         */
        if (tail == size && head == 0) return -1;

        /**
         * 如果tail = size，但是head != 0,说明前有数据删除，队列未满，需要数据迁移
         */
        if (tail == size){
            // head 后面的数据都需要往前迁移 head 位
            for (int i= head;i< size;i++){
                items[i-head] = items[i];
            }
            // 将最后一个元素迁移 head 位
            tail -=head;
            // 第一个元素指向 0
            head = 0;
        }
        // 向队列中添加元素
        items[tail] = data;

        tail++;

        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        // 第一个元素和最后一个元素相等时，队列为空
        if (head == tail) return null;

        String result = items[head];
        // 第一个元素后移一次，这样做的好处是在出队时不需要数据迁移
        head ++ ;

        return result;
    }
}

链式队列

链式队列实现起来相对顺序队列来说要简单很多，我们先来看看链式队列的入队、出队操作：

从图中可以看出链式队列入队操作是将tail的next指向新增的节点，然后将tail指向新增的节点，出队操作时，将head节点指向head.next节点。链式队列与顺序队列比起来不需要进行数据的迁移，但是链式队列增加了存储成本。

基于链表的队列实现代码

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
/**
 * 基于链表的队列
 */
public class LinkQueue {

    // 指向队首
    private Node head;
    // 指向队尾
    private Node tail;

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        Node node = new Node(data,null);
        // 判断队列中是否有元素
        if (tail == null) {
            tail = node;
            head = node;
        }else {
            tail.next = node;
            tail = node;
        }
        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        if (head==null) return null;
        String data = head.data;
        head = head.next;
        // 取出元素后，头指针为空，说明队列中没有元素，tail也需要制为空
        if (head == null){
            tail = null;
        }
        return data;
    }

    class Node{
        private String data;
        private Node next;

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

循环队列

循环队列是对顺序队列的改进，因为顺序队列不可避免的数据迁移操作，数据迁移操作会导致队列的性能下降，为了避免这个问题，将队列改造成循环的，当tail到达数组的最大下标时，重新指回数组下标为0的位置，这样就避免了数据迁移。先来看看循环队列的出队、入队操作：

因为队列是循环队列，所以在进行入队、出队操作时，就不能像顺序队列那样对tail、head进行简单的加1操作，我们需要对tail、head加1后与数组的大小进行求余操作，来得出tail、head的值，这样才能进行循环操作。循环队列需要牺牲一个存储空间，对于一个存储空间为n的循环队列来说只能存放n-1为数据，因为如果不牺牲一个存储空间的话，当tail==head时，就有可能存在队空或者队满的情况。

循环队列的实现代码

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
/**
 * 环形队列,不需要数据迁移，提高性能
 */
public class CircularQueue {

    // 存放数据的数组
    private String[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;
    // 最后一个节点
    private int tail = 0;

    // 构造函数
    public CircularQueue(int size){
        this.size = size;
        items = new String[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        /**
         * 判断环形队列满了的条件，(tail+1)求余等于head
         */
        if ((tail+1)%size == head) return -1;

        // 向队列中添加元素
        items[tail] = data;
        // 因为是环形队列，所以下边是数组长度的余数
        tail= (tail+1)%size;

        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        // 第一个元素和最后一个元素相等时，队列为空
        if (head == tail) return null;

        String result = items[head];
        // 因为是环形队列，所以下边是数组长度的余数
        head = (head+1)% size ;

        return result;
    }
}

双端队列

双端队列是一种队头、队尾都可以进行入队、出队操作的队列，双端队列采用双向链表来实现，先来看一下双端队列的入队、出队操作：

可以从动态图中看出，双端队列的每一端都是一个栈，都符合栈先进后出的特性，如果我们对双端队列进行禁止队头入队和队尾出队操作的限制，双端队列又变成了一个链式队列，双端队列是一种多功能的数据结构，我们可以使用它来提供队列和栈两种功能。

双端队列的实现代码

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
/**
 * 双端队列，使用双向链表实现
 */
public class DoubleEndsQueue {

    private static class Node {
        String item;
        Node next;
        Node prev;

        Node(Node prev, String element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    // 第一个节点
    private Node first;
    // 最后一个节点
    private Node last;

    /*
     * 在第一个节点前面入队
     */
    public void enqueueFirst(String e) {
        final Node f = first;
        final Node newNode = new Node(null, e, f);
        // 第一个节点指向新节点
        first = newNode;
        if (f == null)
            // 最后一个节点也指向该节点
            last = newNode;
        else
            // 当前节点的前节点指向新节点
            f.prev = newNode;
    }

    /**
     * 在最后一个元素后面入队
     * @param e
     */
    public void enqueueLast(String e) {
        final Node l = last;
        final Node newNode = new Node(l, e, null);
        // 最后一个节点指向新节点
        last = newNode;
        if (l == null)
            // 第一个节点指向新节点
            first = newNode;
        else
            // 当前节点的下节点指向新节点
            l.next = newNode;
    }

    /**
     * 从第一个节点出队
     * @return
     */
    public String dequeueFirst() {
        if (first == null) return null;
        final Node f = first;
        String element = f.item;
        Node next = f.next;
        f.item = null;
        f.next = null;
        // 第一个节点指向当先节点的next节点
        first = next;
        if (next == null)
            // 说明队列为空
            last = null;
        else
            next.prev = null;
        return element;
    }

    /**
     * 从最后节点出队
     * @return
     */
    public String dequeueLast() {
        final Node l = last;
        if (last == null) return null;
        String element = l.item;
        Node prev = l.prev;
        l.item = null;
        l.prev = null;
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        return element;
    }
    
    // 输出队列全部内容
    public void displayAll() {
        while (first !=null){
            System.out.print(first.item+" ");
            first = first.next;
        }
        System.out.println("===============");
    }
}

优先队列

优先队列为一种不必遵循队列先进先出(FIFO)特性的特殊队列，优先队列跟普通队列一样都只有一个队头和一个队尾并且也是从队头出队，队尾入队，不过在优先队列中，每次入队时，都会按照入队数据项的关键值进行排序(从大到小、从小到大)，这样保证了关键字最小的或者最大的项始终在队头，出队的时候优先级最高的就最先出队，这个就像我们医院就医一样，急救的病人要比普通的病人先就诊。一起来看看优先队列的出队、入队操作：

在示例中，我们规定数值越小优先级越高。我们每执行一次入队操作时，小的元素都会靠近头队，在出队的时候，元素小的也就先出队。

优先队列的代码实现

这里使用的数组实现优先队列，用数组实现主要原因是更好理解优先队列的思想。一般都是使用堆来实现优先队列，因为数组实现在插入的时候对数据的排序代价比较大。

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
/**
 * 优先队列
 */
public class PriorityQueue {

    // 存放数据的数组
    private Integer[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;

    // 构造函数
    public PriorityQueue(int size){
        this.size = size;
        items = new Integer[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(Integer data){
        int j;
        if (head == 0){
            items[head++] = data;
        }
        else {
            for (j=head-1;j>=0;j--){
                // 将小的数往后排
                if (data > items[j]){
                    items[j+1] = items[j];
                }else {
                    break;
                }
            }
            items[j+1] = data;
            head++;
        }
        return 1;
    }

    public Integer dequeue(){
        return items[--head];
    }
}

总结

  • 队列是一种遵循先进先出(FIFO)的数据结构

  • 队列可以使用数组和链表实现，数组实现叫作顺序队列，链表实现叫作链- 式队列

  • 循环队列解决了顺序队列的数据迁移带来的性能损耗的问题

  • 双端队列是队头和队尾都可以进行入队、出队操作的队列

  • 优先队列是一种不必遵循先进先出规则的队列，任意元素加入时，都会讲- 优先级最高的放入到队头

    参考链接

相关文章
点击查看

本文标题:Java队列实现

文章作者:Liuyang

发布时间:2020年01月11日 - 09:21:42

最后更新:2020年01月11日 - 09:58:36

原始链接:http://yoursite.com/2020/01/11/Java%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%