【数据结构队列介绍 + 手写简单的PriorityQueue

队列

什么是队列

在计算机科学中，队列(queue)  是一种特殊类型的抽象数据类型或集合。集合中的实体对象按顺序保存，可以通过在序列的一端添加实体和从序列的另一端移除实体来进行操作。

队列是一种先进先出(FIFO - First In First Out)的数据结构。

队列特点

• 新元素加入队列末尾。
• 原来队头的元素是下一个出队的元素。

（可以用链表实现，也可以用数组实现）

• 基于数组:固定长度,简单高效。

  • 但是删除对头会导致后面元素前移，时间复杂度较高。
  • 数组可能会进行扩容，效率低
  • 会预留空间，利用率不如链表高

• 基于链表:可变长度,实现更复杂但性能更好。

  • 链表长度可变
  • 删除头部时间复杂度更低

综上: 链表用于实现队列理论上较好，但是实际上呢，使用数组操作会更快一点，毕竟不需要进行new Node()操作。

队列分类

队列还分为 单端队列(queue)  和 双端队列(deque)

• 单端队列: 只能一头进入元素，另一头弹出元素

  Java里面并没有单纯的单端队列实现类，所以我们一般是使用LinkedList或者ArrayDeque来实现单端队列。

  所以我们可以使用双端队列的链表实现类LinkedList，但是呢，我们只用它的两个办法

  • offer() 方法是从队列尾部(rear)添加元素。这与一般的入队操作(enqueue)是等价的。
  • poll() 方法是从队列头部(front)取出元素。这与一般的出队操作(dequeue)是等价的。

  这样就实现了单端队列。

• 双端队列: 可以两头弹出元素或者进入元素

  上次我们手写了LinkedList，将其实现为双向链表，它稍微改造就能成为双端队列,改造如下:

• 添加头插法(addFirst()) 和尾插法(addLast()) 方法,可以在队头和队尾插入元素
• 添加移除队头(removeFirst()) 和 移除队尾(removeLast())方法
• 实现 getFirst() 和 getLast() 方法获取队头和队尾元素(不删除元素)

对列操作

将元素添加到队列后的操作称为入队，从队列中移除元素的操作称为出队。

队列常用的操作有:

• 入队(Enqueue):加入一个新元素到队尾。addLast()

• 出队(Dequeue):删除队头元素。removeFirst()

• 边界操作:

  • 队头(Front):获取队头元素。getFirst(), peek(),element()
  • 队尾(Rear):获取队尾元素。getlast()

队列使用环境

• 实现先进先出的资源调度:比如任务调度、消息队列等。
• 数据缓冲区:当数据很多时，让它们排队，一个一个处理
• 轮询服务，依次发送询问消息

手写一个PriorityQueue

因为之前我们已经手写过LinkedList，在我们之前的基础上添加几个方法就能实现双端队列了，再写也没有什么意思。

然后呢，ArrayDeque我打算在栈的那章手写。

因此，我打算写一个优先队列，这是一个使用数组实现的队列。优先级高的越先被弹出，优先级越低越后被弹出。

优先队列的实现方式

它是由数组实现的，但是该数组结构可以展开成为一个二叉堆结构。

为什么不使用一般数组，而是使用二叉堆形式的数组:

综上所述，我们决定使用二叉堆数组来实现优先队列。

它的结构如下所示:

观察图片，我们可以去找规律，你可以发现设父节点的索引为n，则左子节点的索引为2*n+1， 右子节点的索引为2*n+2。

比如父节点为0， 左子节点为2*n+1 = 1, 右子节点为2*n+2 = 2。找到规律之后就好办了。

然后我们开始手写FakePriorityQueue类。

完成的最终框架是这样:

从上到下依次是:

• 存放数据的数组
• 数组大小
• 比较器
• 构造方法
• 入队方法
• 上滤
• 弹出方法
• 下滤
• 列出数据

构造方法

FakePriorityQueue(Comparator comparator){
    // 源码默认开个11位的, 这样刚好是一个完全二叉树，我自己开18个
    heap = new Object[18];
    this.comparator = comparator;
}

这个构造方法传入了一个比较器，是因为我们在计算优先级时，需要使用比较器来计算。

入队方法

// 入队
public void offer(E e){
    if(size == 0) heap[0] = e;
    else {
        heap[size] = e;
        siftUp(size, e);
    }
    size++;
}

这里的入队里面有一个siftUp方法，我下面再介绍。

这里先判断有无数据，无数据直接顶部设为传入的数据，有数据就进行上升过滤操作。

为什么需要上升过滤呢？

因为我们添加数据默认将数组放在数组末尾:

如图所示: 我们现在添加一个2，我们默认放在数组末尾，但是呢，我们是优先队列,越小的越往上；因此，我们需要把2与6作比较，谁比较小谁就往上移动。

我们发现2比6小，所以交换2和6的位置。

交换完毕，2再与1比较，发现1比较小，所以不用交换了。

上面这个过程就叫上升过滤

下面详细讲解上升过滤的写法。

上升过滤

public void siftUp(int index, E e){
    while (index > 0){
        // 获得父亲节点的下标
        int parentIndex = (index - 1)>>>1;
        // 取出父亲节点的
        E parent = (E) heap[parentIndex];
        // 父亲比孩子大
        if (comparator.compare(parent, e) > 0){
            // 交换父亲与孩子的位置
            heap[parentIndex] = e;
            heap[index] = parent;
            index = parentIndex;
        }else break;
    }
}

逻辑就是不断与父节点相比较，如果父节点大于子节点，就交换他们俩，保证越往上越小。

弹出元素

public E poll(){
    if(size==0) return null;
    // 取出根
    Object root = heap[0];
    // 根变为最后一个元素
    heap[0] = heap[--size];
    // 最后一个元素置为null
    heap[size] = null;
    siftDown(0, (E) heap[0]);
    // 大小减一
    return (E) root;
}

我们弹出元素是弹出优先级最高的，即是我们二叉堆的根节点，然后对剩余的元素进行整理，还原为二叉堆的结构。

首先，把原来的根节点的值赋值为末尾节点的值，让它从上往下过滤，维持二叉堆的结构。

下面写出具体的下降过滤代码:

过滤下降

public void siftDown(int index, E e){
    int half = size>>>1;
    // 这里有个小优化,最后一排元素的索引为n/2到n, 这样当是叶子节点就不会判断了。
    while (index < half){
        // 找出左孩子
        int leftChild = (index  0) minChild = heap[leftChild=rightChild];
        if (comparator.compare(e, (E) minChild)  o.age);
    FakePriorityQueue personPriority = new FakePriorityQueue(comparator);
    personPriority.offer(new Person("花花", 15));
    personPriority.offer(new Person("公国", 10));
    personPriority.offer(new Person("哈哈", 3));
    personPriority.offer(new Person("asd", 4));
    personPriority.offer(new Person("gfdh", 5));
    personPriority.offer(new Person("gfdh", 1));
    personPriority.offer(new Person("gfdh", 7));
    personPriority.offer(new Person("gfdh", 2));
    personPriority.lists();
    System.out.println("==============");
    System.out.println("容量:" + personPriority.size);
    System.out.println("取出栈顶元素:"+ personPriority.poll());
    System.out.println("==============");
    personPriority.lists();
    System.out.print("此时容量:"+personPriority.size);
}

class Person{
    public int age;
    String name;
    Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString(){
        return ("name=" + name + ",age=" + age);
    }
}

输出

name=gfdh,age=1
name=gfdh,age=2
name=哈哈,age=3
name=asd,age=4
name=gfdh,age=5
name=公国,age=10
name=gfdh,age=7
name=花花,age=15
==============
容量:8
取出栈顶元素:name=gfdh,age=1
==============
name=gfdh,age=2
name=asd,age=4
name=哈哈,age=3
name=花花,age=15
name=gfdh,age=5
name=公国,age=10
name=gfdh,age=7
此时容量:7

你把输出的数组以二叉堆的形式表达出来，然后删除栈顶，再看看结构是否是预期结果。

我这里不足的是没有写数组扩容，我在ArrayList那章写了，可以去看看。过程都差不多。

总结