数据结构和算法-4.2-队列

本来想栈和队列写为一篇的，而且也确实这么写了，然而写完还是决定拆分开来比较好，简洁，易读；

队列

• 第一个插入的数据会被最先移除，进行插入操作的端称为队尾，进行删除操作的端称为队头；例如显示中人们排队办理业务，水管中的水流；
• FIFO：first in first out, 先进先出；
• 队列的实现
  1. 先创建一个队列的基类

  public abstract class Queue<T> {
    //是否为空
    public abstract boolean isEmpty();
    //插入
    public abstract void insert(T value);
    //删除
    public abstract T remove();
    //打印队列
    public abstract void display();
  }
  

  2. 用数组实现队列

  public class ArrayQueue<T> extends Queue<T> {
    private int maxSize;
    private T[] queArray;
    private int front;//队列首
    private int rear;//队列尾
    private int nItems;
  
    public ArrayQueue(int maxSize){
        this.maxSize=maxSize;
        queArray=(T[]) new Object[maxSize];
        front=0;
        rear=-1;
        nItems=0;
    }
  
    @Override
    public void insert(T value){
        if (rear==maxSize-1)
            rear=-1;
        queArray[++rear]=value;
        nItems++;
    }
  
    @Override
    public T remove(){
        T temp=queArray[front++];
        if (front==maxSize)
            front=0;
        nItems--;
        return temp;
    }
  
    public T peekFront(){
        return queArray[front];
    }
  
    public int size(){
        return nItems;
    }
  
    @Override
    public boolean isEmpty(){
        return nItems==0;
    }
  
    public boolean isFull(){
        return nItems==maxSize;
    }
  
    /**
     * 打印数组
     */
    @Override
    public void display() {
        System.out.println("ArrayQueue.size: "+size());
        System.out.print("ArrayQueue: ");
        if (size()!=0) {
            for (int i = front; i <= rear; i++) {
                System.out.print("[" + i + "]-->" + queArray[i] + "  ");
            }
        }
        System.out.println();
    }
  }
  

  3. 对上面队列的使用

   private static void testQueue() {
        ArrayQueue<String> queue = new ArrayQueue<>(10);
        for (int i = 100; i < 120; i++) {
            if (!queue.isFull()) {
                queue.insert("data—" + i);
                queue.display();
            }
        }
        System.out.println("peekFront:" + queue.peekFront());
        System.out.println("peekFront:" + queue.peekFront());
        System.out.println("peekFront:" + queue.peekFront());
  
        while (!queue.isEmpty()) {
            System.out.println("remove:" + queue.remove());
            queue.display();
        }
        for (int i = 120; i < 140; i++) {
            if (!queue.isFull()) {
                queue.insert("data-" + i);
                queue.display();
            }
        }
    }
  

• 循环队列：
  注意上面代码中的insert和remove中的if语句，当队首队尾指针达到最值是，将他们设为初始值，这就是循环队列（也称缓冲环），然而如果像上面那样，使用时用isFull和isEmpty进行判断，就可以当作普通队列使用了；
• 双端队列：
  • 队列的每一端都可以插入和删除数据，其元素的逻辑结构仍是线性结构；可以使用双端链表实现，这个在后面介绍链表时会给具体的实现代码，它主要用到四个方法insertLeft(), removeLeft(), insertRight(), removeRight()；
  • 如果禁止insertLeft(),removeLeft()（或right）双端队列的功能就和栈一样了；
  • 如果禁止removeLeft(),insertRight()（或另两个）双端队列的功能就和队列一样了
• 优先级队列：
  • 如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了 优先级队列 这种数据结构。
  • 下面是用数组实现优先级队列的代码，也可以用后面会学到的堆来实现

  public class PriorityArrayQueue <T extends Comparable<T>> {
    private int maxSize;
    protected T[] queArray;
    protected int size;
  
    public PriorityArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        //Java 创建泛型类型的数组方法1:
        queArray = (T[]) new Object[maxSize];
        size = 0;
    }
    public PriorityArrayQueue(int maxSize,T[] a) {
        this.maxSize = maxSize;
        // queArray = (T[]) new Object[maxSize];
        //由于PriorityArrayQueue <T extends Comparable<T>>,
        // 所以上面这条语句是错的，因为不能把Object数组造型为Comparable数组。
        //Java 创建泛型类型的数组方法2:
        queArray= (T[]) Array.newInstance(a.getClass().getComponentType(), a.length);
        size = 0;
    }
  
    /**
     * 插入数据
     * @param value
     */
    public void insert(T value) {
        int j;
        if (size == 0) {
            queArray[size++] = value;
        } else {
            //插入排序
            for (j = size - 1; j >= 0; j--) {
                if (value.compareTo(queArray[j]) > 0)
                    //从队尾开始，依次循环，把所有比新值小的都后移一位，把新值插入移动后空出的位置
                    //如此插入，实现了从大到小排序，又因为remove方法是从队尾开始，这样就实现了优先处理较小值的需求
                    queArray[j + 1] = queArray[j];
                else
                    break;
            }
            queArray[j + 1] = value;
            size++;
        }
    }
  
    /**
     * 删除最小值
     * @return
     */
    public T removeMin() {
        return queArray[--size];
    }
  
    /**
     * 删除指定下标元素
     * @param index
     */
    public void remove(int index) {
        for (int i = index; i < size-1; i++) {
            queArray[i] = queArray[i + 1];
            size--;
        }
    }
  
    /**
     * 查看最小
     * @return
     */
    public T peekMin() {
        return queArray[size - 1];
    }
  
    /**
     * 查看指定
     * @param index
     * @return
     */
    public T peek(int index) {
        return queArray[index];
    }
  
    /**
     * 查找指定值
     */
    public int find(T value) {
        for (int i = 0; i < size; i++)
            if (queArray[i].compareTo(value) == 0)
                return i;
        return -1;
    }
  
  
    /**
     * 是否满了
     * @return
     */
    public boolean isFull() {
        return size == maxSize;
    }
  
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }
  
    /**
     * 队列长度
     * @return
     */
    public int size() {
        return size;
    }
  
    /**
     * 打印数组
     */
    public void display() {
        System.out.println("Stacker.size: " + size);
        System.out.print("Stacker: ");
        if (size != 0) {
            for (int i = size - 1; i >= 0; i--) {
                System.out.print("[" + i + "]-->" + queArray[i] + "  ");
            }
        }
        System.out.println();
    }
  }
  

  优先级队列的使用：

   private static void testPriorityQueue() {
        PriorityArrayQueue<Integer> priorityQueue = new PriorityArrayQueue<>(10);
        priorityQueue.insert(3);
        priorityQueue.display();
        priorityQueue.insert(9);
        priorityQueue.display();
        priorityQueue.insert(5);
        priorityQueue.display();
        priorityQueue.insert(0);
        priorityQueue.display();
        priorityQueue.insert(7);
        priorityQueue.display();
        priorityQueue.insert(2);
        priorityQueue.display();
        while (!priorityQueue.isEmpty()) {
            priorityQueue.removeMin();
            priorityQueue.display();
        }
        priorityQueue.insert(23);
        priorityQueue.display();
        priorityQueue.insert(12);
        priorityQueue.display();
        priorityQueue.insert(29);
        priorityQueue.display();
    }