数据结构之队列

栏目: 数据库 · 发布时间: 5年前

内容简介：CUP的资源是有限的，任务的处理速度与线程的个数并不是线性正相关的。相反，过多的线程反而会导致CPU频繁切换，处理能力下降，所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来预先设置的。当我们向一个固定大小的线程池中请求一个线程的时候，如果线程池中没有空闲资源了，这时候线程池怎么处理这个请求呢？是拒绝请求还是排队请求？各种处理策略是神马呢，这时候就要用到队列了。队列有两个最基本的操作，入队enqueue(),放一个数据到队列的尾部；出队dequeue()，从队列头部取出一个元素。

数据结构之队列

本篇是数据结构与算法之美学习笔记

队列是一种可以实现“先进先出”的存储结构。就排队办理业务，先到的人先办理，不能插队。

CUP的资源是有限的，任务的处理速度与线程的个数并不是线性正相关的。相反，过多的线程反而会导致CPU频繁切换，处理能力下降，所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来预先设置的。

当我们向一个固定大小的线程池中请求一个线程的时候，如果线程池中没有空闲资源了，这时候线程池怎么处理这个请求呢？是拒绝请求还是排队请求？各种处理策略是神马呢，这时候就要用到队列了。

队列有两个最基本的操作，入队enqueue(),放一个数据到队列的尾部；出队dequeue()，从队列头部取出一个元素。

顺序队列和链式队列

队列可以使用数组来实现也可以使用链表来实现，用数组实队列的栈叫做顺序队列，用链表实现的队列叫做链式队列。

使用数组来实现一个队列：

public class ArrayQueue {
    private String[] items;
    private int n = 0;//总大小
    private int head = 0;
    private int tail = 0;

    //申请一个大小为n的数组
    public ArrayQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //如果队列满了返回false
        if(tail == n) return false;
        items[tail] = item;
        ++tail;
        return true;
    }

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

}

队列需要两个指针，一个指向队头，一个指向队尾。

当a、b、c、d一次进入队列之后，队列中的head指针指向下标为0的位置，tail下标为4的位置

当我们调用两次出队操作的之后，队列中的head指针指向下标为2的位置，tail指针位置不变。

随着不停的入队和出队操作，head和tail指针会不断的往后移动移动到最右边，即使数组中还有空闲的空间也不能往队列中添加数据了，那怎么办呢？

我们可以使用数据搬移，当然出队的时候不会出现空间不够的情况也就不用搬移，我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想，上面的出队操作不用变，入队操作可以改成下面的：

public boolean enqueue(String item){
        //tail==n 说明队列满了
        if(tail == n){
            //tail==n&&head==0说明整个队列都是满的
            if(head == 0) return  false;
            //搬移数据
            for (int i = head; i < tail; i++) {
              items[i-head] = items[i];
            }
            //更新tail 和 head
            tail -= head;
            head = 0;
        }

        items[tail] = item;
        ++tail;
        return true;
    }

从上面的代码可以看到，当tail指针移动到数据的最右边之后，如果有新数据插入，我们可以将head和tail之间的数据，整体搬移到数组0到tail-head的位置。

使用链表实现队列：

使用链表实现队列同样需要head和tail指针，分别指向链表的第一个结点和最后一个结点。

入队的时候，tail的next指针指向新的结点，然后tail变成新的结点的next。

出队的时候，head的next结点变成它后面的结点的next结点。

public class LinkedQueue {

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

    //入队
    public void enqueue(String value){
       if(tail == null){
           Node newNode = new Node(value,null);
           head = newNode;
           tail = newNode;
       }else {
           tail.next = new Node(value,null);
           tail = tail.next;
       }
    }
   //出队
    public String dequeue(){
        if(head == null) return null;
        String value = head.data;
        head = head.next;
        if(head == null){
            tail = null;
        }
        return value;
    }

    private static class Node{
        private String data;
        private Node next;

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

        public String getData() {
            return data;
        }
    }
}

循环队列：

上面使用数组来实现的队列，当tail==n的时候，会有数据的搬移操作，这样入队的时候的性能就会收到影响。有没有办法解决呢？可以使用循环队列。

原本的数组是一条直线，有头有尾，现在我们把首位相连组成一个环

当tail == n 的时候，表示队列满了，当 head == tail的时候表示队列是空的。

public class CircleQueue {
    private String[] items;
    private int n = 0;//总大小
    private int head = 0;
    private int tail = 0;

    //申请一个大小为n的数组
    public CircleQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //(tail+1)%n == head表示满了
        if((tail + 1)%n == head) return false;
        items[tail] = item;
        tail = (tail+1)%n;
        return true;
    }

    //出队
    public String dequeue(){
        //head == tail 表示队列为空
        if(head == tail) return  null;
        String res = items[head];
        head = (head+1)%n;
        return res;
    }

}