设计公司logo网站,免费dns解析服务器,个人建设网站成本,百度做网站引流数组模拟环形队列
实现逻辑
创建一个固定大小的数组作为队列的存储空间#xff0c;同时定义队列的头部和尾部指针#xff08;front和rear#xff09;。初始时#xff0c;将头部和尾部指针都设置为0#xff0c;表示队列为空。入队操作#xff08;enqueue#xff09;同时定义队列的头部和尾部指针front和rear。初始时将头部和尾部指针都设置为0表示队列为空。入队操作enqueue 首先判断队列是否已满。如果队列已满无法再添加新的元素直接返回。 队列满的判断 公式(rear 1) % N front说明当队列满时尾部指针的下一个位置就是头部指针的位置。解释由于环形队列的特性当尾部指针到达数组的末尾时需要将尾部指针重新设置为数组的起始位置即尾部指针加1后取模。当取模运算的结果与头部指针相等时表示队列已满。 如果队列未满将新元素添加到尾部指针所指向的位置并将尾部指针后移一位。注意如果尾部指针已经到达数组的末尾需要将尾部指针重新设置为数组的起始位置实现循环利用。 出队操作dequeue 首先判断队列是否为空。如果队列为空无法进行出队操作直接返回。 队列空的判断 公式front rear说明当队列为空时头部指针和尾部指针指向同一个位置即队列中没有有效元素。解释由于队列的初始状态是空的所以头部指针和尾部指针都初始化为0。当进行出队操作时头部指针会递增当头部指针和尾部指针相等时表示队列为空。 如果队列不为空将头部指针所指向的元素取出并将头部指针后移一位。注意如果头部指针已经到达数组的末尾需要将头部指针重新设置为数组的起始位置实现循环利用。 队列长度size 队列的长度可以通过尾部指针减去头部指针来计算但这个结果可能为负数或超过数组的大小。为了得到正确的队列长度需要进行取模运算。具体做法是先计算尾部指针减去头部指针的差值然后对数组的大小取模。 队列中的有效元素个数 公式(rear - front N) % N说明计算尾部指针和头部指针之间的差值并对数组大小取模得到队列中的有效元素个数。解释当进行入队操作时尾部指针会递增当进行出队操作时头部指针会递增。通过计算尾部指针减去头部指针的差值可以得到队列中的有效元素个数。由于差值可能为负数或超过数组的大小所以需要对数组大小取模确保结果在合法范围内。
为什么需要用到取模运算实现 取模运算的作用是将超出数组大小的索引重新映射到数组的合法索引范围内实现队列的循环利用。 在环形队列中当尾部指针后移时需要考虑数组的边界情况。如果不进行取模运算当尾部指针达到数组的末尾时无法再继续后移导致队列无法正常工作。 通过取模运算可以将尾部指针重新定位到数组的起始位置使得队列能够形成环形结构。具体来说取模运算可以将尾部指针的值限制在合法范围内即在 0 到 (maxSize-1) 的范围内循环。 例如假设数组的大小为5且当前尾部指针的位置为4即指向数组的最后一个元素。如果不进行取模运算将直接将尾部指针加1即 4 1 5超出了数组的索引范围。但是如果进行取模运算即 (4 1) % 5 0尾部指针会重新定位到数组的起始位置形成环形结构。 因此通过取模运算可以确保尾部指针始终在合法的索引范围内使得环形队列的入队操作能够正常进行。 同样的道理对于头部指针的后移操作也需要进行取模运算以保证在环形队列中正确移动。 代码实现
1定义环形队列
public class CircularQueue {private int[] queue; // 存储队列元素的数组private int front; // 头部指针private int rear; // 尾部指针private int maxSize; // 队列的最大容量public CircularQueue(int capacity) {maxSize capacity 1; // 预留一个位置用于判断队列满queue new int[maxSize];front 0;rear 0;}// 入队操作public void enqueue(int element) {if (isFull()) {System.out.println(队列已满无法入队);return;}queue[rear] element;rear (rear 1) % maxSize; // 尾部指针后移并取模}// 出队操作public int dequeue() {if (isEmpty()) {System.out.println(队列为空无法出队);return -1;}int element queue[front];front (front 1) % maxSize; // 头部指针后移并取模return element;}// 判断队列是否为空public boolean isEmpty() {return front rear;}// 判断队列是否已满public boolean isFull() {return (rear 1) % maxSize front;}// 获取队列中的有效元素个数public int size() {return (rear - front maxSize) % maxSize;}
}
2使用环形队列
public class Main {public static void main(String[] args) {CircularQueue queue new CircularQueue(5); // 创建容量为5的环形队列queue.enqueue(1); // 入队操作queue.enqueue(2);queue.enqueue(3);queue.enqueue(4);queue.enqueue(5);System.out.println(队列是否为空 queue.isEmpty()); // 判断队列是否为空System.out.println(队列是否已满 queue.isFull()); // 判断队列是否已满System.out.println(队列中的有效元素个数 queue.size()); // 获取队列中的有效元素个数while (!queue.isEmpty()) {int element queue.dequeue(); // 出队操作System.out.println(出队元素 element);}}
}
