数据结构与算法-队列

一、基本介绍

        定义 队列是一个遵循“先进先出”（First-In-First-Out, FIFO）原则的线性数据结构。简单来说，元素按照一定的顺序加入到队列的一端（称为尾部或后端），然后从另一端（称为头部或前端）按照加入的先后顺序逐个移除。

操作 队列支持以下主要操作：

• addQueue(element): 将一个元素添加到队列的尾部。
• getQueue(): 从队列的头部移除并返回一个元素。
• headQueue(): 查看队列头部的元素但不移除（某些实现中提供）。
• isEmpty(): 检查队列是否为空。
• showQueue: 展示所有队列数据

二、队列的特点

1. 有限制的插入与删除： 队列对插入和删除操作的位置有严格的限制，这种约束使得队列能有效地管理需要按顺序处理的任务或事件。

2. FIFO性质： 遵循先进先出原则是队列的核心特性，确保了最早加入队列的元素会被优先处理，这对于维护数据处理的公平性和一致性至关重要。

3. 动态变化： 随着enqueue和dequeue操作的进行，队列的大小会动态改变，适应不同的应用场景需求。

三、队列的实现原理与方式

数组实现

• 利用数组可以创建一个静态或循环队列。静态队列当空间不足时可能无法继续入队，而循环队列通过设置合适的索引计算方法避免了这个问题。

四、操作流程

1. 初始化队列结构：

   • 创建一个固定大小的数组来存储队列中的元素。
   • 定义三个关键变量：front（队头指针，初始值为0）、rear（队尾指针，初始值为0）以及maxSize（数组的容量，即队列的最大容量）。

2. 入队操作（addQueue）：

   • 判断队列是否已满（(rear + 1) % maxSize == front），如果队列已满，则不能入队。
   • 如果队列未满，将新元素存入数组中rear指向的位置，然后通过取模运算更新rear指针：rear = (rear + 1) % maxSize。

3. 出队操作（dequeue）：

   • 判断队列是否为空（front ==rear），如果队列为空，则不能出队。
   • 如果队列非空，获取并返回front位置的元素，然后通过取模运算更新front指针：front = (front + 1) % maxSize。

4. 判断队列状态：

   • 通过比较front和rear可以判断队列是空还是满。当它们相等时，若之前有元素进出过队列，则队列为空；否则，需要考虑“约定位置”情况，即在初始化时增加一个额外的空间使得rear+1与front相等表示队列满。

5. 获取队列长度：

   • 计算有效元素个数时，需考虑到环形结构，计算方法通常为(rear - front + maxSize) % maxSize，确保无论rear位于front之前还是之后都能得到正确的结果。

五、 代码展现

1.构造一个队列

//构造队列
class CircleArrayQueue {
    private int maxSize;   //表示数组最大容量
    //队列头 指向队列的第一个元素，也就是arr[front] front初始值=0
    private int front;
    //队列尾 指向队列最后一个元素的最后一个位置，因此空出一个空间作为约定 rear初始值=0
    private int rear;
    private int[] arr;     //该数组用于存放数据,模拟队列
    //    队列构造
    public CircleArrayQueue(int arrMaxSize) {
        arr = new int[arrMaxSize];
        maxSize = arrMaxSize;
    }
}

2.判断队列状态 

    //    判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
 
    //    判断队列是否为空
    public boolean isNull() {
        return front == rear;
    }

3.入队操作 

    //    数据入队列
    public void addQueue(int n) {
 
        if (isFull()) {
            System.out.println("队列已经满了，无法添加数据!");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

4.出队操作 

    //    数据出队列
    public int getQueue() {
        if (isNull()) {
            System.out.println("队列是空的，无法获取数据!");
            throw new RuntimeException("队列是空的，无法获取数据!");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

5.获取队列有效个数，头部队列及展示所有队列

    //    求出当前队列有效个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
 
    //    显示队列头部数据
    public int headQueue() {
        if (isNull()) {
            System.out.println("队列是空的，无法获取数据!");
            throw new RuntimeException("队列是空的，无法获取数据!");
        }
        return arr[front];
    }
    
    //展示队列
    public void showQueue() {
        if (isNull()) {
            System.out.println("队列是空的，无法遍历!");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

 六、总结

        队列作为经典的数据结构，在诸多领域发挥着不可或缺的作用，其简洁高效的特性使其成为了软件设计与开发过程中的得力工具。理解队列的工作原理并熟练运用，对于提升程序性能和解决复杂问题具有重要意义。

        以上展示的是队列介绍，实现原理及相关重要代码的展示。