type
status
date
slug
summary
tags
category
icon
password
数组实现环形队列 详细讲解
数组模拟环形队列
对前面的数组模拟队列的优化,将数组看做是一个环形的。(通过取模的方式来实现即可)
解题思路
1、既然是环形队列,那就一定有头有尾,有容量
2、既然是数组实现,那一定有个算法保证可以让数组循环起来

如图所示:
rear为7 ,front为0,实际的数据为7,是因为rear定义指向了最后一个元素的后一个位置,所以满数组的size变成了size-1,空出的位置来保证循环

- front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
- rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 0
- 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
- 对队列为空的条件, rear == front 空
- 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
- 我们就可以在原来的队列上修改得到,一个环形队列
代码实现
package com.qf; import java.util.Scanner; public class CircleQueue { private int maxSize; private int front; private int rear; private int[] arr; /** * 环形队列的实现 */ //初始化环型队列 public CircleQueue(int maxSize){ this.arr=new int[maxSize]; this.maxSize=maxSize; this.front=0; this.rear=0; } //队列是否已满 public boolean isFull(){ return (rear+1)%maxSize==front; } //队列是否为空 public boolean isEmpty(){ return rear==front; } //入队 public void addQueue(int num){ if (isFull()){ System.out.println("队列已满,请稍等~~~"); }else{ arr[rear]=num; rear=(rear+1)%maxSize; } } //出队 public int outQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空,不能出队~~"); } int outNum=arr[front]; System.out.println("出队的数值为:"+outNum); front=(front+1)%maxSize; return outNum; } //循环队列有效元素 public void showQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空~~"); } for (int i = front; i < front+size(); i++) { System.out.printf(" " +arr[i%maxSize]); } } //得到对头的元素 public int getHeader(){ if (isEmpty()){ throw new RuntimeException("队列为空~~"); } System.out.println("对头元素:"+arr[front%maxSize]); return arr[front%maxSize]; } //得出有效元素的个数 public int size(){ return (rear+maxSize-front)%maxSize; } public static void main(String[] args) { CircleQueue queue = new CircleQueue(4); boolean loop=true; char sc=' '; while (loop){ System.out.println("e 跳出循环"); System.out.println("a 入队"); System.out.println("o 出队"); System.out.println("s 循环队列"); System.out.println("h 展示队头"); Scanner systemPut=new Scanner(System.in); sc=systemPut.next().charAt(0); switch (sc){ case 'a': System.out.println("请输入数据:"); Scanner addNum=new Scanner(System.in); int num = addNum.nextInt(); queue.addQueue(num); break; case 'o': queue.outQueue(); break; case 's': queue.showQueue(); break; case 'h': queue.getHeader(); break; case 'e': loop=false; break; default : break; } } } }
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0%E7%8E%AF%E5%BD%A2%E9%98%9F%E5%88%97%20%E8%AF%A6%E7%BB%86%E8%AE%B2%E8%A7%A3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。