Java_队列(Queue)详解

目录

前言

队列(Queue)

概念

队列的使用

循环队列

循环队列的构思

代码的实现

双端队列(Deque)

概念

方法

?双端队列的使用

---

前言

超详细地讲解了循环队列,为什么要有循环队列 , 普通队列 , 双端队列

队列(Queue)

概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

先入先出,后入后出? 与栈正好相反

?

?跟现实生活中的排队一样:

?

队列的使用

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口(队列底层是链表实现的)

public static void main(String[] args) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(1);
    q.offer(2);
    q.offer(3);
    q.offer(4);
    q.offer(5); // 从队尾入队列
    System.out.println(q.size());
    System.out.println(q.peek()); // 获取队头元素
    q.poll();
    System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
    if(q.isEmpty()){
        System.out.println("队列空");
    }else{
        System.out.println(q.size());
    }
}

循环队列

特点以及为什么要有循环队列

循环队列底层是数组,具有内存固定，效率高等特点

直接用链表来当队列底层,固然很方便,但我们也知道链表在添加节点的时候需要动态分配内存，这个过程是比较耗费资源和时间的

因此如果我们的队列长度固定，又想要有较高的性能，那么就可以用顺序表示方式的队列(循环队列应运而生)

若用户无法预估队列的具体长度，那么用链队列是比较方便的，因为链表的好处就是可以很方便地添加和删除新的节点

循环队列的构思

代码的实现

OJ题链接:设计循环队列

class MyCircularQueue {
    private int[] arr;
    private int left;//队头
    private int right;//伪队尾,指向浪费的空间  真队尾在伪队尾的前一个
    
    public MyCircularQueue(int k) {
        arr = new int[k+1];//留一个空间 防止满的时候队尾和队头在相同位置 
        //队尾队头在相同位置时：数组为空
        //队尾 在 队头 左边一个位置时：数组已满
    }
    
    public boolean enQueue(int value) {//插入一个元素
        if (isFull()) {
            return false;
        }
        arr[right] = value;
        right = (right + 1) % arr.length;
        return true;
    }
    
    public boolean deQueue() {//删除第一个（队列 先进先出）
        if (isEmpty()) {
            return false;
        }
        left = (left + 1) % arr.length; 
        return true;
    }
    
    public int Front() {//返回队首
        if (isEmpty()) {
            return -1;
        }
        return arr[left];

    }
    
    public int Rear() {//返回队尾
        if (isEmpty()) {
            return -1;
        }
        if (right == 0) {//如果right下标为0了则再往前就是数组的最后一个元素
            return arr[arr.length-1];
        }
        return arr[(right-1) % arr.length];//因为我们浪费了一个空间来实现循环队列,所以队尾要往前走一步
    }
    
    public boolean isEmpty() {//队列是否为空
        if (left == right) {
            return true;
        }
        return false;
    }
    
    public boolean isFull() {//队列是否已满
        if ((right+1) % arr.length == left) {//看看伪队尾的下一个元素是不是队头
            return true;
        }
        return false;
    }
}

双端队列(Deque)

概念

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
?

方法

?双端队列的使用

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

具体的使用可以结合上面的方法来用,用法与队列(Queue)一致,在此不再赘述