前言

本博客是学习韩顺平老师的数据结构与算法教程后记录的

队列介绍

队列是一个有序列表，可以用数组或是链表来实现遵循先入先出的原则，即：先存入队列的数据要先取出，后存入的要后取出

使用数组实现队列

class ArrayQueue { /** * 队列头 */ private int front; /** * 队列尾 */ private int rear; /** * 数组总长度 */ private int maxSize; /** * 数组 */ private int[] array; /** * desc : 初始化队列 * create_user : cheng * create_date : 2020/6/30 13:57 */ public ArrayQueue(int maxSize) { this.maxSize = maxSize; this.array = new int[maxSize]; this.front = -1; this.rear = -1; } /** * desc : 判断队列是否已满 * create_user : cheng * create_date : 2020/6/30 14:19 */ public boolean isFull() { return rear == maxSize - 1; } /** * desc : 判断队列是否为空 * create_user : cheng * create_date : 2020/6/30 14:20 */ public boolean isEmpty() { return front == rear; } /** * desc : 添加一个元素 * create_user : cheng * create_date : 2020/6/30 14:20 */ public void addQueue(int item) { // 判断队列是有已满 if (isFull()) { System.out.println("队列已满,添加失败"); return; } // 尾指针后移,添加数据 array[++rear] = item; } /** * desc : 获取一个元素 * create_user : cheng * create_date : 2020/6/30 14:22 */ public int getQueue() { // 判断队列是否为空 if (isEmpty()) { throw new RuntimeException("队列为空"); } // 头指针后移,获取数据 return array[++front]; } }

优化

上述队列存在的明显问题就是数组只能使用一次,使用算法,将数组优化成环形队列(采用取模%的方式) 可以简单类比成钟表,方便理解

class ArrayQueue2 { /** * 队列头,指向队列的第一个元素,array[front]就是队列的第一个元素 */ private int front; /** * 队列尾,指向队列的最后一个元素的后一个位置 */ private int rear; /** * 数组总长度 */ private int maxSize; /** * 数组 */ private int[] array; /** * desc : 初始化队列 * create_user : cheng * create_date : 2020/6/30 14:49 */ public ArrayQueue2(int maxSize) { // 数组的总长度要比实际传入的队列大小+1,因为采用这种方式时,rear尾指针所指向的位置总是空的 maxSize++; this.maxSize = maxSize; array = new int[maxSize]; } /** * desc : 判断队列是否已满 * create_user : cheng * create_date : 2020/6/30 14:19 */ public boolean isFull() { // 如果尾指针下一个元素就是front,那么说明队列已满,实际上这个时候队列还是有一个空的位置 return (rear + 1) % maxSize == front; } /** * desc : 判断队列是否为空 * create_user : cheng * create_date : 2020/6/30 14:20 */ public boolean isEmpty() { return front == rear; } /** * desc : 添加一个元素 * create_user : cheng * create_date : 2020/6/30 14:20 */ public void addQueue(int item) { // 判断队列是否已满 if (isFull()) { System.out.println("队列已满,添加失败"); return; } // 没满就添加数据 array[rear] = item; // 后移尾指针 rear = (rear + 1) % maxSize; } /** * desc : 获取一个元素 * create_user : cheng * create_date : 2020/6/30 14:22 */ public int getQueue() { // 判断队列是不是空的 if (isEmpty()) { throw new RuntimeException("队列为空"); } // 获取队列的第一个元素 int value = array[front]; // 后移头指针 front = (front + 1) % maxSize; // 返回元素 return value; } public int size() { // 尾指针位置 - 头指针位置 // 加上maxSize 防止模出负数 因为这是一个环形队列, 尾指针的值可能小于头指针的值 return (rear - front + maxSize) % maxSize; } }