用数组来模拟循环队列
在循环队列中,保留一个单元。即队列中还有一个位置的时候,就默认认为队列已满
判断队列已满的条件
private int maxSize;// 队列容量,队列可存放数据的大小是队列容量-1 private int front;// 队列头,起始为0,表示队列第一个有值的元素的位置 private int rear;// 队列尾,起始为0,表示队列最后一个有值的元素的下一个位置 private int[] arr;// 存放数据模拟队列重点理解如何判断队列满和求出当前队列有多少个元素
(rear + 1) % maxSize == front可以理解成,队尾已经绕了一圈赶到了队列头的位置,则队列已满(注意保留一个空闲的位置)
建议忽略 %maxSize 来理解 即rear的下一个位置是front时,循环队列已满
取模的原因是保证队列的头和尾在这个数组的范围内
判断队列有多少个元素
(rear + maxSize - front) % maxSize先不取模来理解,同样用上图,队列有多少个元素可以简单理解成rear-front,考虑到rear可能在front的前面,于是加上maxSize 再对整个值取模来表示当前队列有多少个元素
掌握这两个难点后即可模拟队列
完整代码如下
package com.queue; import java.util.Scanner; //模拟环形队列 public class CircleQueueDemo { public static void main(String[] args) { // 模拟队列的实现 CircleQueue aq = new CircleQueue(4); Scanner sc = new Scanner(System.in); int input; boolean flag = true; while (flag) { System.out.println("请输入操作,1 查看整个队列 2 增加元素 3 元素出队列 4 查看头部"); input = sc.nextInt(); switch (input) { case 1: aq.showQueue(); break; case 2: System.out.println("请输入要增加的数字"); int in = sc.nextInt(); aq.add(in); break; case 3: try { int queue = aq.getQueue(); System.out.println(queue + "出队列了"); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 4: try { int showHead = aq.showHead(); System.out.println("头部是" + showHead); } catch (Exception e) { System.out.println(e.getMessage()); } break; default: break; } } sc.close(); } } class CircleQueue { private int maxSize;// 队列容量 private int front;// 队列头,起始为0,表示队列第一个有值的元素的位置 private int rear;// 队列尾,起始为0,表示队列最后一个有值的元素的下一个位置 private int[] arr;// 存放数据模拟队列 public int getRear() { return rear; } public void setRear(int rear) { this.rear = rear; } public CircleQueue(int maxSize) { this.maxSize = maxSize;// 传入的容量设置为队列容量,但预留最后一个空间为空 front = 0;// 指向队列头部的位置 rear = 0;// 指向队列尾部的下一个位置,并且空出最后一个空间 arr = new int[maxSize];// 设置存放数据的数组的大小 } // 判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front;// 可带数字验算得出,比如容量为4,只能装3个元素。当front是0,rear是3时则满了,因为arr[0]和arr[1],arr[2]都装了 // 再比如,front是1,有3个元素arr[1],arr[2],arr[0],此时rear是0(下标3的下一个就变回0) } // 判断队列是否为空 public boolean isEmpty() { return front == rear;// 头和尾指向同一个位置证明是空 } // 添加数据到队列 public void add(int n) { // 如果满了则不能添加 if (isFull()) { System.out.println("满了,不能加数据"); return; } arr[rear] = n;// 把数据放入最后一个有元素的位置的下一个(即rear) rear = (rear + 1) % maxSize;// 后移,但要考虑取模问题 } // 数据出队列 public int getQueue() { // 如果为空,则抛出异常 if (isEmpty()) { throw new RuntimeException("队列为空,没有数据可以出队列"); } int val = arr[front]; arr[front] = 0; front = (front + 1) % maxSize;// 取完数据后,让头部向下一个位置移动,考虑取模的问题 return val; } // 显示队列的所有数据 public void showQueue() { // 如果为空 if (isEmpty()) { System.out.println("队列空,没数据显示"); return; } // 从front开始,遍历有多少个值 for(int i = front;i<=front + showValuesCount();i++) { System.out.println("arr ["+ i%maxSize + "]的值是 "+arr[i%maxSize]); } } // 求出当前队列有多少个值 public int showValuesCount() { return (rear + maxSize - front) % maxSize;//假如maxsize是4,front是1,rear是3,即当前arr[1]和arr[2]是有值的,值的个数为2 } // 显示头数据,不是取数据 public int showHead() { // 如果为空 if (isEmpty()) { throw new RuntimeException("队列为空,没有头数据"); } return arr[front]; } }
全部评论
(0) 回帖