数据结构学习(循环队列)
1. 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定
2. 这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front [满]
rear == front [空]
package cn.imut; //循环队列 import java.util.Scanner; public class CircleArrayQueueDemo { public static void main(String[] args) { System.out.println("测试数组模拟循环队列的案例"); //创建一个队列 CircleArray circlequeue = new CircleArray(4); //这里设置4,其队列的有效数据最大是3 var key = ‘ ‘; //接收用户输入 Scanner sc = new Scanner(System.in); boolean loop = true; //输出一个菜单 while(loop){ System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = sc.next().charAt(0); //接收一个字符 switch (key){ case ‘s‘: circlequeue.showQueue(); break; case ‘a‘: System.out.println("输入一个数"); int value = sc.nextInt(); circlequeue.addQueue(value); break; case ‘g‘: try{ int res = circlequeue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case ‘h‘: try{ int res = circlequeue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case ‘e‘: sc.close(); loop = false; break; default: break; } } System.out.println("程序退出!"); } } class CircleArray{ private int maxSize; //表示数组最大容量 //front指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front的初始值=0 private int front; //队列头 //rear指向队列的最后一个元素的后一个位置,希望腾出一个空间作为约定,rear的初始值=0 private int rear; //队列尾 private int[] arr; //该数组用于存储数据,模拟队列 /* * 取数据时front改变,加数据时rear改变 * 在循环队列中,为了判断队列满和队列空的情况,对队列少用一个元素空间,使头指针指向队头元素的前一个位置,当尾指针等于该位置时就表示队满。 */ //创建队列的构造器 public CircleArray(int arrMaxSize){ maxSize = arrMaxSize; //初始化为0,不用重新赋值 arr = new int[maxSize]; } //判断队列是否满 public boolean isFull(){ return (rear + 1) % maxSize == front; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //添加数据到队列 public void addQueue(int n){ //判断队列是否已满 if(isFull()){ System.out.println("队列已满!"); return; } //直接将数据加入即可 arr[rear] = n; //将rear后移,这里必须考虑取模 (防止数组越界) rear = (rear + 1) % maxSize; } //获取队列的数据,出队列 public int getQueue(){ //判断队列是否为空 if(isEmpty()){ //通过抛出异常 throw new RuntimeException("队列为空,不能取数据"); } //这里需要分析front是指向队列的第一个元素 //1.先把front对应的值保存到一个临时变量 //2.将front后移,考虑取模 //3.将临时保存的变量返回 int value = arr[front]; front = (front + 1) % maxSize; return value; } //显示队列的所有数据 public void showQueue(){ //遍历 if(isEmpty()){ System.out.println("队列为空,没有数据..."); return; } //思路:从front开始遍历 for(int i = front; i < front + size(); i++){ System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]); } } //求出当前队列有效数据个数 public int size(){ //eg: rear = 1 front = 0 maxSize = 3 //(尾 + 最大值 - 头) % 最大值 return (rear + maxSize - front) % maxSize; } //显示队列的头数据(不是取数据) public int headQueue(){ //判断 if(isEmpty()){ throw new RuntimeException("队列为空,没有数据..."); } return arr[front]; } }
相关推荐
ipqtjmqj 2020-03-23
hanyujianke 2020-02-25
niushao 2020-01-10
whtqsq 2019-09-07
zzpdljd 2019-08-02
meridian00 2019-07-01
lickylin 2019-07-01
基尔霍夫的猫 2019-06-28
鱼天翱 2019-06-21
hanyujianke 2017-10-27
PHP100 2019-03-28
大故事家 2018-05-13
btr的心灵鸡杂汤 2018-05-04
大故事家 2017-11-29
BAT 批处理程序 2017-06-19