Java 队列Queue从原理到实战指南_Java

一、队列的认识

队列的底层与集合框架

在 java 中，队列（queue）是集合框架的一部分，属于 java.util 包下的接口。

从底层实现来看，不同的队列实现类底层数据结构不同。但是主要是由链表和数组实现的.
linkedlist 实现了 queue 接口，它底层基于双向链表，通过节点的链接来维护队列的先进先出（fifo）特性，插入和删除元素时效率较高.
arraydeque 则底层基于数组，利用数组的索引操作来模拟队列，在首尾操作元素时也能有较好的性能。

集合框架为队列提供了统一的接口规范，让开发者能方便地使用队列的各种操作，如入队（offer）、出队（poll）、查看队首元素（peek）等，同时也能结合集合框架中的其他类和接口，实现更复杂的数据结构和算法操作。

java集合框架

常见的队列方法

queue(栈)中在java中常见的方法有add,offer .remove,poll .element , peek.他们两两一组,又有不同的次重点.
这几个方法都是java中queue接口定义的方法，它们的不同点主要体现在操作失败时的表现以及方法用途侧重方面：

插入元素方法对比（add和offer）

add(e e)：
- 操作失败时的表现：如果试图将元素添加到一个容量固定且已满的队列中，会抛出illegalstateexception异常。例如，当使用arraydeque创建一个固定大小的队列，并且队列已经达到最大容量时，调用add方法添加元素就会触发异常。
- 用途侧重：适用于在程序中能明确保证队列不会满的场景，或者希望在队列满时以异常形式来中断程序流程，从而进行错误处理的情况。
offer(e e)：
- 操作失败时的表现：当尝试将元素添加到已满的队列中，不会抛出异常，而是返回false 。比如在实现一个任务队列，当队列满时，不希望程序因为添加任务失败而崩溃，此时可以使用offer方法，通过返回值来判断任务是否成功添加。
- 用途侧重：更适合在日常开发中，不确定队列是否已满的场景，通过返回值来灵活处理添加操作的结果。

移除元素方法对比（remove和poll）

remove()：
- 操作失败时的表现：如果从空队列中移除元素，会抛出nosuchelementexception异常。比如在编写一个处理消息队列的程序时，没有提前检查队列是否为空就直接调用remove方法，当队列为空时就会引发异常。
- 用途侧重：适用于能确保队列非空的场景，或者希望以异常的方式来处理空队列情况，提醒开发者进行相应的错误处理。
poll()：
- 操作失败时的表现：从空队列中移除元素时，不会抛出异常，而是返回null 。例如，在循环处理队列元素时，可以使用poll方法，通过判断返回值是否为null来确定是否已经处理完所有元素，进而结束循环。
- 用途侧重：在不确定队列是否为空的情况下使用更方便，通过返回值就能轻松判断操作结果，避免了繁琐的异常处理代码。

查看队首元素方法对比（element和peek）

element()：
- 操作失败时的表现：当试图从空队列中获取队首元素时，会抛出nosuchelementexception异常。例如，在一个多线程操作队列的场景中，没有做好同步控制，在队列为空时调用element方法就会出现异常。
- 用途侧重：适用于确定队列非空的场景，用于获取队首元素进行后续操作，并且希望以异常形式来处理空队列的情况。
peek()：
- 操作失败时的表现：从空队列中获取队首元素时，不会抛出异常，而是返回null 。比如在一个定时检查队列头部元素的任务中，使用peek方法可以在不抛出异常的情况下，简单判断队列是否为空以及获取队首元素。
- 用途侧重：在不确定队列是否为空，又需要获取队首元素信息时，使用peek方法更为合适，方便根据返回值进行后续逻辑处理。

简单说就是

add/remove/element：操作失败会抛异常。
offer/poll/peek：操作失败返回 false（offer）或 null（poll/peek），更安全。

二、方法简单实现

linkedlist实现

框架搭建

public class myqueue {
    // 使用linkedlist实现的队列，存储整数类型元素
    // linkedlist实现了queue接口，提供了队列的基本操作 向上转型
    queue<integer> queue = new linkedlist<>();
    //静态内部类
    static class listnode{
        public int val;
        public listnode prev; //链表中的两个重要指向
        public listnode next;
        public listnode(int val){
            //构造方法 用于实例化对象
            this.val = val;
        }
    }
    public listnode first;
    public listnode last;
}

工具代码

  public boolean isempty(){
        return first ==  null && last ==null;
    }
    public int size(){
        int count = 0;
        listnode cur = first;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

尾差offer

public void offer(int val){
        listnode node = new listnode(val);
        if (isempty()){
           first = last = node;
        }else {
           last.next = node;
           node.prev = last;
           last = node;
        }
    }

头删poll

public int poll(){
        int val = first.val;
        if (isempty()){
            return -1;
        }
        if (first == last){
            first = null;
            last = null;
        }else {
            first = first.next;
            first.prev = null;
        }
        return val;
    }

取顶pop

public int pop(){
        if (isempty()){
            return -1;
        }
        else {
            return first.val;
        }
    }

核心思想
这里方法核心思想就是链表中指向的修改问题,在定义的first,last cur三个指向的修改思想.比如:

数组实现遇到的问题

数组的结构不像链表那样灵活,尤其是头删,我们的指针会不断的向后面进行,导致前面的内存浪费.
比如说;假设我们有一个固定大小的数组来模拟队列，设置队首指针 front 和队尾指针 rear，初始时都指向数组起始位置。当进行入队操作时，rear 不断后移；出队操作时，front 也不断后移。可这样一来，随着操作的进行，队列前面会逐渐出现空闲的空间，但因为 rear 已经到达数组末尾，我们却无法再利用这些前面的空闲空间，就好像队列 “假满” 了一样，明明数组还有空间，却无法继续入队新元素。
其次，当队列中的元素都出队后，front 和 rear 都指向了数组后面的位置，此时队列实际为空，但从指针位置看，却好像还有元素存在，这就给我们判断队列是否为空带来了困难。
为了解决这些问题，循环队列的概念就被引入了。循环队列把数组的首尾连接起来，形成一个环形的结构，让队首和队尾指针可以循环移动，从而充分利用数组的空间，也能更方便、准确地判断队列的空满状态。

三、引入循环队列

两个问题

从上面的图可以看出有两个棘手的问题

1.当入队的时候,rear不断向后,传统的思想就是每次有新的元素进队,我们使rear+1即可,但是当rear一个单位相邻front时候,我们再让下边+1就不是front(默认下表0)的下标了,头删问题同上.
2.我们应当如何判断队列是不是满的,而不是不同的覆盖添加.

如何正确表示下边(从尾部到头部)?

公式法
(r + 偏移量) % len
(f + 偏移量) % len

如何判断队列满不满?

标记法
在rear = front (起始时) tip = !isfull标记一下,当下一次出现rear = front时, tip = isfull.不再进行插入

预留空间法
在循环队列中让rear的下一位就是front,即(rear+1)%len = front

预留空间法实现

代码示例

public class mycircularqueue {
    //预留空间法
    //初始变量的定义
    public int [] elem;
    public int rear ;
    public int front;
    //构造方法进行初始化
    public mycircularqueue(int k){
        this.elem = new int [k];
    }
    /****
     * 入队
     */
    public boolean enqueue(int val) {
        //判满
        if (isfull()) {
            return false;
        }
        elem[rear] = val;
        rear = (rear + 1) % elem.length;
        return true;
    }
    //出队
    public boolean dequeue (){
        if (isempty()){
            return false;
        }
        front = (front+1)%elem.length;
        return true;
    }
    /****
     * 返回头
     * @return
     */
    public int getfront(){
        if (isempty()){
            return -1;
        }
        return elem[front];
    }
    /****
     * 返回尾
     * @return
     */
    public int getrear(){
        if (isempty()){
            return -1;
        }
        if (rear == 0)
            return elem[elem.length-1];
                    //处理边界问题
        }else {
            return elem[rear-1];
        }
    }
    public boolean isfull(){
        //r的下一个是f
        return (rear+1)%elem.length == front;
    }
    public boolean isempty(){
        return front == rear;
    }
}

标记法实现

代码示例

public class mycircularqueue {
    //标记法
    //初始变量的定义
    public int [] elem;
    public int rear ;
    public int front;
    //构造方法进行初始化
    public mycircularqueue(int k){
        this.elem = new int [k];
    }
	private boolean isfull0 = false;
    public boolean isfull2(){
        //r的下一个是f
        return isfull0;
    }
    public boolean isempty2(){
        return front == rear && !isfull0;
        }
    //标记法
    public boolean enqueue2(int val) {
        //判满
        if (isfull2()) { //一开始进不来
            return false;
        }
        elem[rear] = val;
        rear = (rear + 1) % elem.length;
        //入队后判断是不是满了
        if (rear == front) {
            isfull0 = true;
        }
        return true;
    }
    //出队
    public boolean dequeue2 (){
        if (isempty()){
            return false;
        }
        front = (front+1)%elem.length;
        isfull0 = false;
        return true;
    }
}