Java代码实现循环队列的示例代码_Java教程

Java代码实现循环队列的示例代码

2022-01-20 01:071 Byte Java教程

队列作为基础的数据结构，是程序员的入门课。也是所有程序员必须掌握的一种数据结构，队列在程序中广泛应用，因此我们应该对队列有深入的了解，接下来我们通过代码来对队列这种数据结构进行深度解析，感兴趣的朋友一起

循环队列结构

Java代码实现循环队列的示例代码

队列特点

队列为一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

循环队列优缺点

循环队列的优点：

可以有效的利用资源。用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据。

循环队列的缺点：

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，判别队列是"空"是"满"需要特殊处理 —— 判断队列为空的条件还是head == tail，但是判断队列已满的条件则是(tail+1)%size==head。

应用场景

最经典的就是类似于约瑟夫环的问题，可以使用循环队列。

Java代码实现循环队列

				?

									// 基于数组实现一个循环链表

									public class CircleArrayQueue<T> {

									    // 定义数组用于存放数据

									    private T[] arr;

									    private int head;  // 记录队列头

									    private int tail;  // 记录队列尾

									    private int size;  // 数组大小

									    // 循环链表初始化

									    public CircleArrayQueue(int cap){

									        this.arr = (T[])new Object[cap];

									        this.head = 0;

									        this.tail = 0;

									        this.size = cap;

									    }

									    // 入队方法

									    public void offer(T data){

									        // 判断循环队列是否已满，满了就直接return

									        if((tail + 1) % size == head){

									            return;

									        }

									        arr[tail] = data;     // 向尾加入元素

									        tail = (tail + 1) % size; // 将尾指针后移1，考虑端点情况处理

									    }

									    // 出队方法

									    public T poll(){

									        // 循环队列为空则直接返回null

									        if(isEmpty()){

									            return null;

									        }

									        T pollData = arr[head];   // 找到出队元素

									        arr[head] = null;         // 清除出队位置的元素

									        head = (head + 1) % size; // 将尾指针后移1，考虑端点情况处理

									        return pollData;

									    }

									    // 判断循环队列是否为空

									    public boolean isEmpty(){

									        return head == tail;

									    }

									    // 测试

									    public static void main(String[] args) {

									        CircleArrayQueue<String> arrayQueue = new CircleArrayQueue<>(5);

									        arrayQueue.offer("a");

									        arrayQueue.offer("b");

									        arrayQueue.offer("c");

									        arrayQueue.offer("d");

									        arrayQueue.offer("e");

									        arrayQueue.offer("f");

									        System.out.println(arrayQueue);

									        String poll1 = arrayQueue.poll();

									        System.out.println("出队元素：" + poll1);

									        String poll2 = arrayQueue.poll();

									        System.out.println("出队元素：" + poll2);

									    }

									}