什么是队列

队列(Queue)是一种特殊的数据结构,它遵循先进先出(FIFO,First In First Out)的原则。这意味着队列的第一个元素是最先被添加的,也是最先被移除的,而队列的最后一个元素是最后被添加的,也是最后被移除的。我举一个比较通俗易懂的例子,就是你排队去买早餐,先来的先买,后来的去排队再买,这就是一个生活中的小事例。为了加深大家的印象,我画了一张队列的图如下所示:
Snipaste_2024-07-19_21-33-24.png
从图中可以看出队列也是一种操作受限制的线性表结构,入队和出队被限制在两端进行,而栈被限制在一端进行入栈,出栈。那如何实现队列,请看下面讲解。

队列的实现方式:

1.通过模拟数组来实现.
首先我们初始化一个数组,并设定一个数组的最大内存空间,然后给定一个head队头指针,tail队尾指针,初始值head=0,tail=0,那接下来如何入队,如何出队呢?我们要先思考一下,什么情况下可以入队呢,当然是队列空间没满的情况,那出队呢,队列不为空。用head和tail如何表示?当tail head,队列为空,(tail+1)最大内存空间时,队列满了。了解完了入队,出队的执行条件后,我们用图来演示入队,出队,如图所示:
初始状态:
Snipaste_2024-07-19_23-08-06.png
插入了三个元素入队之后tail指针的指向如图所示:
Snipaste_2024-07-19_23-10-55.png

arr[tail++]=插入的数据值

删除元素data1时 head指向如图所示:
Snipaste_2024-07-19_23-12-40.png

head++;

看到这里,眼睛比较尖的小伙伴可能会有疑问,那出队之后的内存空间是不是浪费掉了?答案是,是的。有没有什么好的解决方法呢?小伙伴们此刻可以自己暂停一下,花个几分钟思考一下。
我来揭晓答案了,我们可以用循环队列来解决,就是将一个线性的队列转换成一个圆形的队列,如图所示:
Snipaste_2024-07-20_16-14-54.png
那要写出不出错误的队列操作代码,我觉得关键是要找到队满,队空的条件。在非循环队列队空的条件是headtail,在循环队列中也一样,但是队满就不一样。非循环队列是tailmaxSize(最大内存空间),而循环队列是(tail+1)%maxSizehead,大家可以自己在纸上画一画得出该结论,我相信你们的智慧。
有了以上的知识储备后,代码就很好写了。我做了一个小总结,代码如下:

public class CircularQueue {
    private int[] queue;//初始化一个数组
    private int front;//队头指针
    private int rear;//队尾指针
    private int capacity;//最大内存空间

    public CircularQueue(int capacity) {//初始化该类的属性值
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public boolean enqueue(int item) {//入队的方法
        if (isFull()) {//如果满了,入队失败
            return false;
        }
        queue[rear] = item;
        rear = (rear + 1) % capacity;
        return true;
    }

    public int dequeue() {//出队的方法
        if (isEmpty()) {//如果队空,则出队失败.
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        return item;
    }

    public boolean isEmpty() {//队头队尾值相等则队空
        return front==rear;
    }

    public boolean isFull() {//判断队满
        return (rear + 1) % capacity == front;
    }

    public static void main(String[] args) {
        CircularQueue cQueue = new CircularQueue(5);

        // 入队操作
        cQueue.enqueue(1);
        cQueue.enqueue(2);
        cQueue.enqueue(3);

        // 出队操作
        System.out.println("Dequeued item: " + cQueue.dequeue());

        // 继续入队操作
        cQueue.enqueue(4);
        cQueue.enqueue(5);
        cQueue.enqueue(6);

        // 尝试入队,队列已满
        System.out.println("Enqueue 7: " + cQueue.enqueue(7)); // 应返回false
    }
}

2.通过Java封装的常用容器:
实现接口Queue的有类PriorityQueue,也叫优先队列,是一种将元素有序排列的队列,默认的是小根堆,也就是从小到大进行排序。还有类LinkedList,也叫双链表,维护的元素值无序排列。
常见的封装使用函数有:
add():在队尾添加元素
remove():删除并返回队头
isEmpty():是否为空
size():返回长度
peek():返回队头
clear():清空
这种实现队列的方式是不是很简单啊。学习了创建队列后,我们还要了解它的使用场景,这就好比知己知彼,百战不殆。

队列的应用场景:

在操作系统中,队列可以用来管理待执行的任务或进程,确保它们按照特定的顺序执行。在打印系统中,队列用于存储待打印的文档,按照先来先服务(FCFS)的原则进行打印。在网络协议栈中,队列用于缓冲发送和接收的数据包,以处理网络流量和数据传输。在分布式系统和微服务架构中,消息队列用于异步传输消息,确保系统的解耦和扩展性。在多线程或多进程编程中,队列用于协调生产者和消费者之间的工作,避免竞争条件。还有其它的应用场景,就不一一列举了,经常使用的场景就这些。

今日小结:

今天我给大家入门讲解了队列这种数据结构,介绍了它的基本操作如入队,出队,还有如何实现队列,一种是用数组模拟循环队列来提高数组空间的利用率,另一种是直接调用Java语言中的封装类中的方法。知道了如何实现队列之后,我们就了解了它的使用场景,例如在打印机工作时,先排队的任务先执行,后来的任务后执行。欢迎大家一起讨论队列的其他使用场景,咱们江湖有缘再见。

发表回复

后才能评论