Java_队列(Queue)详解

2023-12-21 18:39:35

目录

前言

队列(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)一致,在此不再赘述

文章来源:https://blog.csdn.net/qq_48858380/article/details/135010091
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。