队列的实现

什么是队列？

队列很好理解，虽然他是一个抽象的数据结构，不过可以把它想象成“排队”：先来的先买，后来的后买，不能插队。遵循先进先出原则，这就是队列。

队列的基本操作

队列有两个基本操作：入队(enqueue)和出队(dequeue);
入队：把一个数据放到队列尾部；
出队：把一个数据从头部移除；

1.png

队列的实现形式

• 顺序队列
  用数组实现的队列叫顺序队列

public class ArrayQueue implements IQueue {

    private String[] items;//存储的数组
    private int n = 0;//数组长度
    private int head = 0;//头指针
    private int tail = 0;//尾指针

    public ArrayQueue(int size) {
        items = new String[size];
        this.n = size;
    }

    //入队
    @Override
    public void enqueue(String value) {
        if (tail == n) {
            //队列末尾没有空间了
            if (head == 0) {
                //整个数组满了
                return;
            }
            //当出队后，head前面有空间，把数据搬移到从下标0开始
            for (int i = head; i < tail; i++) {
                items[i - head] = items[i];//head开始的数据往0开始搬移
            }
        }

        items[tail] = value;
        tail++;
    }

    //出队
    @Override
    public String dequeue() {
        if (head == tail) {
            return null;//队列为空
        }
        String value = items[head];
        head++;
        return value;
    }

    public StringBuilder toString1() {
        StringBuilder sb = new StringBuilder();
        for (int i = head; i < tail; i++) {
            sb.append(items[i]).append(",");
        }
        return sb;
    }
}

注意点：
因为有出队操作，所以head不可能一直是0，所以当tail到达尾部，head!=0时，head前面还有剩余空间，我们在进行一次入队操作时，需要循环把后面的数据搬移到从0开始的位置。

2.jpg

• 链式队列
  用链表实现的队列叫链式队列

public class LinkedQueue implements IQueue {

    private Node head = null;
    private Node tail = null;

    /**
     * 链式队列没有数量限制，直接new
     */
    public LinkedQueue() {}

    @Override
    public void enqueue(String value) {
        Node newNode = new Node(value);

        if (head == null) {
            //队列为空时
            head = newNode;
            tail = newNode;
            return;
        }

        tail.next = newNode;//尾部添加新节点
        tail = tail.next;//tail指向尾部
    }

    @Override
    public String dequeue() {

        if (head == null) {
            return "null";
        }

        String value = head.value;
        head = head.next;//head指向下一个节点
        return value;
    }

    public StringBuilder toString1() {

        StringBuilder sb = new StringBuilder();
        Node node = head;
        while (node!= null) {
            sb.append(node.value).append(",");
            node = node.next;
        }
        return sb;
    }
}

• 循环队列
  我们把队列的头尾相连，形成一个环的队列叫循环队列。
  循环队列的好处是：当tail在尾部时，避免了顺序队列的搬移数据操作。

3.jpg

public class CircleQueue implements IQueue {

    private String items[];
    private int n;
    private int head = 0;
    private int tail = 0;

    public CircleQueue(int size) {
        this.n = size;
        items = new String[size];
    }

    @Override
    public void enqueue(String value) {

        //判断是否满了
        if ((tail + 1) % n == head) {
            return;
        }
        items[tail] = value;
        tail = (tail + 1) % n;
    }

    @Override
    public String dequeue() {

        if (head == tail) {
            return "null";//队列为空
        }
        String value = items[head];
        head = (head + 1) % n;
        return value;
    }

    public StringBuilder toString1() {

        StringBuilder sb = new StringBuilder();
        for (int i = head; i != tail; i = (i + 1) % n) {
            sb.append(items[i]).append(",");
        }
        return sb;
    }
}

循环队列的难点在于：如何判断队列是空的还是满的；

因为在数组中，还是有头尾的，只是用head和tail指针，让数组看起来像个圆。当tail=n，在数组尾部时，单纯的tail+1不能实现循环（超出了数组的长度，引发数组越界）。所以，需要把tail指向数组的下标0，即：tail=(tail + 1) % n;

所以每次指针的移动，都需要在+1的基础上%n 取余数。

4.jpg

• 阻塞队列
  在上面的基础队列中添加阻塞操作。
  当队列为空时，从队列中获取数据就会被阻塞，直到有数据了，才返回。
  当队列数据已满，想要再插入队列也会被阻塞，直到队列中有空闲位置，才允许插入。

• 并发队列
  在多线程操作队列时，为了线程安全，一般给队列的操作加上锁，同一时刻仅允许一个线程操作。

总结

基于链表的无界队列，在数量上可以说是无限的。但也会导致任务过多的堆积，如果在响应时间敏感的系统上，则不是那么合适。

基于数组的有界队列，在设计队列的数量上需要好好研究，数量太大，导致的数据过大，实际项目中等待的任务过多；数量太小，又无法发挥资源的利用。

源码地址：https://github.com/space0o0/dataStructure