数据结构之队列

队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。
队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

存储原理

队列这种数据结构既可以用数组来实现，也可以用链表来实现
1）数组实现

image.png

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置
用数组实现的队列叫作顺序队列
2）链表实现

image.png
用链表实现的队列叫作链式队列

操作

1）入队
入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

image.png

2）出队
出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

image.png

完整代码

数组实现

package com.david.line.queue;

/**
* 用数组实现的队列
*/
public class ArrayQueue {
    // 数组:items,数组大小:n
    int[] nums;
    // head表示队头下标，tail表示队尾下标
    int head = 0;
    int tail = 0;

    //申请一个大小为capacity的数组
    public ArrayQueue(int size) {
        nums = new int[size];
    }

    //入队
    public boolean enqueue(int n) {
        // 如果tail == n 表示队列已经满了
        if (tail == nums.length) return false;
        nums[tail] = n;
        ++tail;
        return true;
    }

    //出队
    public int dequeue() {
        // 如果head == tail表示队列为空
        if (head == tail) return 0;

        int ret = nums[head];
        ++head;
        return ret;
    }

    public static void main(String[] args) {
        ArrayQueue aq = new ArrayQueue(8);
        aq.enqueue(3);
        aq.enqueue(5);
        aq.enqueue(1);
        aq.enqueue(4);

        System.out.println(aq.dequeue());
        System.out.println(aq.dequeue());
        System.out.println(aq.dequeue());
        System.out.println(aq.dequeue());
    }
}

链表实现

package com.david.line.queue;

import com.david.line.queue.Node;

/**
* 链表实现
*/
public class LinkedQueue {
    Node head;
    Node tail;
    int size;

    public void enqueue(Node node) {
        if (tail == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

    public Node dequeue() {
        if (head == null) return null;
        Node h = head;
        //将拉取的节点的下一个节点变成新的表头
        head = head.next;
        //把旧的表头的下一个节点指向设置为null，让gc回收
        h.next = null;
        //队列为空
        if (head == null) {
            tail = null;
        }

        size--;
        return n;
    }

    public static void main(String[] args) {
        Node n1 = new Node(3);
        Node n2 = new Node(5);
        Node n3 = new Node(1);
        Node n4 = new Node(4);

        LinkedQueue lq = new LinkedQueue();
        lq.enqueue(n1);
        lq.enqueue(n2);
        lq.enqueue(n3);
        lq.enqueue(n4);

        System.out.println(lq.dequeue().value);
        System.out.println(lq.dequeue().value);
        System.out.println(lq.dequeue().value);
        System.out.println(lq.dequeue().value);
    }
}

时间复杂度

入队和出队都是O(1)

应用

资源池、消息队列、命令队列等等