算法专题-手动实现循环队列 _循环队列

文章插图

这次我就使用数组来实现静态队列了。值得注意的是：往往实现静态队列，我们都是做成循环队列。这道题也是我多次面试过程中遇到的，比如字节跳动和猿辅导，希望大家掌握。
为什么静态队列要做成循环队列呢？试想，底层依赖数组，如果不做成循环的，会非常浪费空间，那我们得申请多大的内存啊？既然做成循环的，首先我们得解决几个问题，如何判空？如何判满？最多可以存放多少元素个数？

文章插图

通过这幅图，想必大家很容易理解，下面通过代码说明。
public class MyQueue { public int[] arrays; public int front;//指向第一个有效元素 public int rear;//指向最后一个有效元素的下一个元素（无效元素） public MyQueue(int[] arrays, int front, int rear) { this.arrays = arrays; this.front = front; this.rear = rear; } /** * 判断队列是否满了 * @param myQueue * @return */ public static boolean isFull(MyQueue myQueue){ if((myQueue.rear + 1) % myQueue.arrays.length == myQueue.front){ return true; }else{ return false; } } /** * 判断是否为空 * @param myQueue * @return */ public static boolean isEmpty(MyQueue myQueue){ if(myQueue.rear == myQueue.front){ return true; }else{ return false; } } /** * 入队 * @param myQueue * @param value */ public static void enQueue(MyQueue myQueue, int value){ //不是满的队列才入队 if(!isFull(myQueue)){ myQueue.arrays[myQueue.rear] = value; myQueue.rear = (myQueue.rear + 1) % myQueue.arrays.length; } } /** * 遍历 * @param myQueue */ public static void traverse(MyQueue myQueue){ int i = myQueue.front; while(i != myQueue.rear){ System.out.print(myQueue.arrays[i] + " "); i = (i + 1) % myQueue.arrays.length; } System.out.println(); } public static void outQueue(MyQueue myQueue){ if(!isEmpty(myQueue)){ int value = https://www.isolves.com/it/cxkf/sf/2019-12-19/myQueue.arrays[myQueue.front]; System.out.println(value); myQueue.front = (myQueue.front + 1) % myQueue.arrays.length; } } public static void main(String[] args) { MyQueue myQueue = new MyQueue(new int[6], 0, 0); System.out.println(isEmpty(myQueue)); enQueue(myQueue, 1); enQueue(myQueue, 2); enQueue(myQueue, 3); enQueue(myQueue, 4); enQueue(myQueue, 5); System.out.println(isFull(myQueue)); traverse(myQueue); outQueue(myQueue); }}输出结果：

文章插图

从上面的设计我们可以发现：rear并不指向最后一个有效的元素，在循环队列中这样设计是非常方便的！因为这样设计可以让我们分得清队头和队尾(不然循环队列不断入队或出队，位置是变化很快的)
由于我们是循环队列，所以front和rear值会经常变动，我们得把front和rear的值限定在一个范围内，不然会超出队列的长度的。
我们通过这种方式：rear=（rear+1)%数组长度
比如rear的下标是2，数组的长度是6，往后面移一位是3，那么rear = （rear+1) % 6，结果还是3 。

【算法专题-手动实现循环队列】