数据结构Java版（3）——队列Queue

一、概念

? ? ? ? 队列也是一种线性数据结构，最主要的特点是入队列顺序和出队列顺序是相同的，操作时在队尾入队，在队首出队。在Java中给我们提供了一个泛型队列——Queue，其中最常用的方法有：

1. void offer()：入队
2. E poll()：出队
3. E peek()：查看队首元素
4. int size()：返回队中元素
5. boolean isEmpty()：检查队列是否为空

二、队列的实现

? ? ? ?因为队列也是一种线性结构，所以这里可以利用之前我们写的数组，这里可以用接口的方式来实现我们自己的顺序队列，下面进行代码演示。

队列的接口

public interface Queue_i<Elem> {
    public abstract boolean offer(Elem e);
    public abstract Elem poll();
    public abstract Elem peek();
    public abstract int getLength();
    public abstract boolean isEmpty();
    public abstract Elem peekLast();
}

通过接口的方式，对queue中的方法进行重写，实现功能?

public class ArrQueue<E> implements Queue_i<E>{
    private MyArray<E> queue;
    private int length;

    public ArrQueue() {
        this.queue = new MyArray<>(16);
        length = 0;
    }

    @Override
    public boolean offer(E e) {
        try{
            this.queue.add(e);
        }catch (Exception exception){
            return false;
        }
        length++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) return null;
        E e;
        try{
            e = this.queue.removeByIndex(0);
        }catch (Exception exception){
            return null;
        }
        this.length--;
        return e;
    }

    @Override
    public E peek() {
        if (isEmpty()) return null;
        E e;
        try{
            e = this.queue.getValueByIndex(0);
        }catch (Exception exception){
            return null;
        }
        return e;
    }

    @Override
    public int getLength() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        return getLength()==0;
    }

    @Override
    public E peekLast() {
        if (isEmpty()) return null;
        E e;
        try{
            e = this.queue.getValueByIndex(this.length-1);
        }catch (Exception exception){
            return null;
        }
        return e;
    }
}

?对自己的顺序队列进行代码测试?

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class testMyQueue {
    public static void test(Queue_i<Integer> queue, List<Integer> list){
        Random random = new Random();
        for(int i = 0;i < 10;i++){
            queue.offer(random.nextInt(1000));
            System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
        }
        Integer temp;
        while ((temp = queue.poll())!=null){
            list.add(temp);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        Queue_i<Integer> queue = new ArrQueue<>();
        test(queue,list);
        for (Integer i:list) {
            System.out.println(i);
        }
    }
}

输出结果：

? ? ? ? 通过观察可知，队列具有先进先出的特点。

三、循环队列

? ? ? ? ?因为顺序队列每次出队时都要把所有元素向前移动一位，时间复杂度高，但如果用双指针，则会导致假溢出现象出现，为了解决这个问题，我们提出了循环队列这个概念。

通过接口的方式，对queue中的方法进行重写，实现功能?

public class LoopQueue<T> implements Queue_i<T>{
    private MyArray<T> queue;
    private int front;
    private int rear;

    public LoopQueue() {
        this.queue = new MyArray<>(17);
        this.front = 0;
        this.rear = 0;
    }

    @Override
    public boolean offer(T t) {
        try{
            queue.add(rear, t);
        }catch (Exception e){
            return false;
        }
        rear =  (rear + 1)%queue.getSize();
        return true;
    }


    @Override
    public T poll() {
        if(isEmpty()) return null;
        T t;
        try{
            t = queue.removeByIndex(front);
        }catch (Exception e){
            return null;
        }
        front = (front+1)%queue.getSize();
        return t;
    }

    @Override
    public T peek() {
        if(isEmpty()) return null;
        T t;
        try{
            t = queue.getValueByIndex(front);
        }catch (Exception e){
            return null;
        }
        return t;
    }

    @Override
    public int getLength() {
        return (rear + queue.getSize() - front)%queue.getSize();
    }

    @Override
    public boolean isEmpty() {
        return rear==front;
    }

    @Override
    public T peekLast() {
        if(isEmpty()) return null;
        T t;
        try{
            t = queue.getValueByIndex((rear - 1 + queue.getSize())%queue.getSize());
        }catch (Exception e){
            return null;
        }
        return t;
    }
}

? ? ? ? 这里需要注意的时，因为循环队列两个指针能循环使用的原因，我们判断队列是否为空和为满时会出现冲突，即两个条件都是rear==front，为了解决这个问题，我们牺牲了一个空间，以区别为空和为满，则为空条件不变，为满条件变为（rear+1）%总容量==front，这个就导致我们在数组扩容时出现问题，这里有两个解决方案，一是将数组中的方法进行重新，二是将数组的长度初始值设为一，以填补浪费掉的空间。这里还有一个注意点是要重新数组中的删除方法，仅删除不调动位置。

对循环队列的测试

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class testMyQueue {
    public static void test(Queue_i<Integer> queue, List<Integer> list){
        Random random = new Random();
        for(int i = 0;i < 10;i++){
            queue.offer(random.nextInt(1000));
            System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
        }
        Integer temp;
        while ((temp = queue.poll())!=null){
            list.add(temp);
        }
        System.out.println();
    }

    public static void test(Queue_i<Integer> queue){
        List<Integer> list = new ArrayList();
        Random random = new Random();
        for(int i = 0;i < 20;i++){
            queue.offer(random.nextInt(1000));
            System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
        }
        Integer temp;
        while ((temp = queue.poll())!=null){
            list.add(temp);
        }
        for (Integer i:list) {
            System.out.println(i);
        }

    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        Queue_i<Integer> queue = new ArrQueue<>();
        Queue_i<Integer> queue2 = new LoopQueue<>();
        test(queue2);
//        test(queue,list);
//        for (Integer i:list) {
//            System.out.println(i);
//        }
    }
}

输出结果：

四、队列可以解决的问题

1.进行异步操作，在多线程编程时减少线程阻塞现象

? ? ? ? 这里具体操作可以去看之前一篇浏览器事件循环的文字，其中对浏览器的异步操作进行了详细讲解，其中就用到了队列的知识：

浏览器事件循环-CSDN博客