数据结构(队列)

一.什么是队列

1.队列定义

        队列是一种特殊的线性表，特殊之处在于他只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。和栈一样，队列也是一种操作受限制的线性表。进行插入操作的一端称为队尾，进行删除操作的一端称为队头或者队首。

2.队列特点

        ①   队列中的元素满足先进先出(FIFO)的特点,即先进入队列的元素总是最先从队列移出。这种特点使得队列在处理数据时具有优势，能够高效地组织和管理进程。同时，先进先出也保证了队列中元素的顺序稳定，避免了一些特护情况下的数据丢失。

        ② 限制插入和删除操作：队列只允许在队尾插入元素，在队头删除元素。

        ③ 应用广泛：队列在计算机领域中应用广泛，如操作系统、网络通信、数据压缩等，在实际生活中，排队买票、办理业务等也可以用队列来模拟和处理。

二.队列的基本操作 

1.首先定义一个队列接口，编写队列的几种基本操作

public interface myQueue<T> {// 入队void offer(T val);// 出队T poll();// 查看队首元素T getFront();// 获取当前队列中的元素个数int getSize();// 判断队列是否为空boolean isEmpty();}

2.我们创建一个类去实现我们自己撰写的接口

// 以数组为队列的数据存储结构
public class ArrOrdQueue<T> implements myQueue<T> {private MyArray<T> data;int size;public ArrOrdQueue() {this.data = new MyArray<>(100);this.size = 0;}@Overridepublic void offer(T val) {this.data.add(val);this.size++;}@Overridepublic T poll() {if(isEmpty()){return null;}return this.data.removeFromLast();}@Overridepublic T getFront() {if(isEmpty()){return null;}return this.data.getValue();}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}}

 3.入队操作

    // 添加元素public void add(T item) {this.arr[this.size] = item;this.size++;}

4. 判断队列是否为空

    // 判空public boolean isEmpty() {return this.size == 0;}

5.出队操作

    public T removeFromLast() {T delVal = this.arr[this.size - 1];this.size--;return delVal;}

6. 查看当前队头元素

    public T getValue() {return getValueByIndex(this.size - 1);}// 获取指定位置的值public T getValueByIndex(int index) {// 入参判断if (index < 0 || index > capacity) {throw new IllegalArgumentException("索引异常！");}return this.arr[index];}

7.获取当前队列中元素的个数

    // 获取元素个数public int getSize() {return this.size;}

 三.队列的应用

        ① 图的遍历算法中的广度优先搜索就可以用队列辅助。

        ② 可用于计算机的模拟。

        ③ 可作为CPU的作业调度。使用队列来处理，可实现先到先执行的要求