重温数据结构—队列

队列的介绍

队列的结构很好理解，就像日常排队一样，规则就是先进先出。对于队列只支持进队列和出队列操作，进队就是插入一个数据到队列尾部，出队就是从队列头部取一个数据。所以队列本质上和栈一样是一个受限的线性表数据结构。

队列的使用场景

队列在日常开发工作中经常使用，主要的使用场景集中在实时性要求不是特别高又要有高并发要求，例如各个系统的日志推送到集中日志中心、业务系统发送短信、两个业务关联系统进行业务结果的异步通知、作为服务请求方和服务提供方之间的压力缓冲等等应用场景。当然还有一种场景就是作为循环队列用于高速存取，例如Disruptor和Linux的环形缓存。

队列的实现

队列因为本质上是线性数据结构，所以在实现上其实主要也是有两种实现一种是基于数组的实现，一种是基于链表的实现。具体的实现代码如下，代码本身是比较简单的，没有特别复杂的逻辑，直接看代码就能够明白。

基于数组的队列

基于数组的队列有一点需要考虑就是在入队和出队的时候计算数据数组存放和取出位置的时候，需要利用队头和队尾进行取模才能计算出存放或取出的位置，不然随着队头和队尾不断增长，长度会超过队列总长度。

public class ArrayQueue {
    private String[] datas;
    private int head;
    private int tail;
    private int count;

    public ArrayQueue(int size){
        datas = new String[size];
        count = 0;
        head = 0;
        tail = 0;
    }

    public boolean enqueue(String data){
        if(count==0){
            //空队列
            datas[head] = data;
            count++;
            return true;
        }else if(count==datas.length){
            //队列满了
            return false;
        }else{
            datas[++tail%datas.length] = data;
            count++;
            return true;
        }

    }

    public String dequeue(){
        if(count==0){
            //空队列
            return null;
        }else{
            String data = datas[head];
            head = ++head%datas.length;
            count--;
            return data;
        }
    }

    public void printQueue(){
        for(int i=0;i<count;i++){
            System.out.println(datas[(head+i)%datas.length]);
        }
    }
}

基于链表的队列

public class LinkedListQueue {

    private Node head = null;
    private Node tail = null;
    private int size = 5;
    private int count = 0;

    public boolean enqueue(String data){
        if(count==size){
            //队列满了
            return false;
        }
        if(count==0){
            //空队列
            Node node = new Node(data,null);
            head = node;
            tail = node;
            count++;
        }else{
            tail.next = new Node(data, null);
            tail = tail.next;
            count++;
        }
        return true;
    }

    public Node dequeue(){
        if(count==0){
            return null;
        }else{
            Node node = head;
            head = head.next;
            count--;
            return node;
        }
    }

    public int getSize(){
        return this.size;
    }

    public class Node {
        public String data;
        public Node next;

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