关于算法:看动画学算法之队列queue

2次阅读

共计 2920 个字符，预计需要花费 8 分钟才能阅读完成。

队列 Queue 是一个十分常见的数据结构，所谓队列就是先进先出的序列构造。

设想一下咱们日常的排队买票，只能向队尾插入数据，而后从队头取数据。在大型项目中罕用的消息中间件就是一个队列的十分好的实现。

一个队列须要一个 enQueue 入队列操作和一个 DeQueue 操作，当然还能够有一些辅助操作，比方 isEmpty 判断队列是否为空，isFull 判断队列是否满员等等。

为了实现在队列头和队列尾进行不便的操作，咱们须要保留队首和队尾的标记。

先看一下动画，直观的感受一下队列是怎么入队和出队的。

先看入队：

再看出队：

能够看到入队是从队尾入，而出队是从队首出。

和栈一样，队列也有很多种实现形式，最根本的能够应用数组或者链表来实现。

先考虑一下应用数组来存储数据的状况。

咱们用 head 示意队首的 index，应用 rear 示意队尾的 index。

当队尾一直插入，队首一直取数据的状况下，很有可能呈现上面的状况：

下面图中，head 的 index 曾经是 2 了，rear 曾经到了数组的最初面，再往数组外面插数据应该怎么插入呢？

如果再往 rear 前面插入数据，head 后面的两个空间就节约了。这时候须要咱们应用循环数组。

循环数组怎么实现呢？只须要把数组的最初一个节点和数组的最后面的一个节点连贯即可。

有同学又要问了。数组怎么变成循环数组呢？数组又不能像链表那样前后连贯。

不急，咱们先思考一个余数的概念，如果咱们晓得了数组的 capacity，当要想数组插入数据的时候，咱们还是照常的将 rear+1，然而最初除以数组的 capacity, 队尾变到了队首，也就间接的实现了循环数组。

看下 java 代码是怎么实现的：

public class ArrayQueue {

    // 存储数据的数组
    private int[] array;
    //head 索引
    private int head;
    //real 索引
    private int rear;
    // 数组容量
    private int capacity;

    public ArrayQueue (int capacity){
        this.capacity=capacity;
        this.head=-1;
        this.rear =-1;
        this.array= new int[capacity];
    }

    public boolean isEmpty(){return head == -1;}

    public boolean isFull(){return (rear +1)%capacity==head;
    }

    public int getQueueSize(){if(head == -1){return 0;}
        return (rear +1-head+capacity)%capacity;
    }

    // 从尾部入队列
    public void enQueue(int data){if(isFull()){System.out.println("Queue is full");
        }else{
            // 从尾部插入
            rear = (rear +1)%capacity;
            array[rear]= data;
            // 如果插入之前队列为空, 将 head 指向 real
            if(head == -1){head = rear;}
        }
    }

    // 从头部取数据
    public int deQueue(){
        int data;
        if(isEmpty()){System.out.println("Queue is empty");
            return -1;
        }else{data= array[head];
            // 如果只有一个元素，则重置 head 和 real
            if(head == rear){
                head= -1;
                rear = -1;
            }else{head = (head+1)%capacity;
            }
            return data;
        }
    }
}

大家留神咱们的 enQueue 和 deQueue 中应用的办法：

rear = (rear +1)%capacity
head = (head+1)%capacity

这两个就是循环数组的实现。

下面的实现其实有一个问题，数组的大小是写死的，不可能动静扩容。咱们再实现一个可能动静扩容的动静数组实现。

    // 因为是循环数组，这里不能做简略的数组拷贝
    private void extendQueue(){
        int newCapacity= capacity*2;
        int[] newArray= new int[newCapacity];
        // 先全副拷贝
        System.arraycopy(array,0,newArray,0,array.length);
        // 如果 real<head, 示意曾经进行循环了，须要将 0 -head 之间的数据置空，并将数据拷贝到新数组的相应地位
        if(rear< head){for(int i=0; i< head; i++){
                // 重置 0 -head 的数据
                newArray[i]= -1;
                // 拷贝到新的地位
                newArray[i+capacity]=array[i];
            }
            // 重置 real 的地位
            rear= rear+capacity;
            // 重置 capacity 和 array
            capacity=newCapacity;
            array=newArray;
        }
    }

须要留神的是，在进行数组扩大的时候，咱们不能简略的进行拷贝，因为是循环数组，可能呈现 rear 在 head 前面的状况。这个时候咱们须要对数组进行非凡解决。

其余局部是和一般数组实现根本一样的。

除了应用数组，咱们还能够应用链表来实现队列，只须要在头部删除和尾部增加即可。

看下 java 代码实现：

public class LinkedListQueue {
    //head 节点
    private Node headNode;
    //rear 节点
    private Node rearNode;

    class Node {
        int data;
        Node next;
        //Node 的构造函数
        Node(int d) {data = d;}
    }

    public boolean isEmpty(){return headNode==null;}

    public void enQueue(int data){Node newNode= new Node(data);
        // 将 rearNode 的 next 指向新插入的节点
        if(rearNode !=null){rearNode.next=newNode;}
        rearNode=newNode;
        if(headNode == null){headNode=newNode;}
    }

    public int deQueue(){
        int data;
        if(isEmpty()){System.out.println("Queue is empty");
            return -1;
        }else{
            data=headNode.data;
            headNode=headNode.next;
        }
        return data;
    }
}

下面的 3 种实现的 enQueue 和 deQueue 办法，基本上都能够立马定位到要入队列或者出队列的地位，所以他们的工夫复杂度是 O(1)。

本文的代码地址：

learn-algorithm