数组方式实现队列操作

 

   

一、队列的介绍

 我们在超市付款时，先排队的总是先付款完成（排除插队），队列的一个特点就是“先进先出，后进后出”

特点

队列是一个有序列表，可以通过数组和链表来实现遵循”先进先出，后进后出的原则“如图在用数组表示队列时，总是在底部插入数据，在顶部拿出数据

　　　　　　

 

 

 

二、数组模拟队列分析

MaxSize是数组的长度，那MaxSize-1就是队列的最大下标了，front和rear是队列前后的下标，front是取出数据时改变，rear时添加数据时改变

添加数据时：

首先判断队列是否满，怎么判断是否满？

　　　　　　　　　　尾指针rear随着添加数据而增加，当rear指向队列最大下标时为满，即rear==Maxsize

不满时，尾指针rear初始值指向-1，所以添加前需要先将进行上移（即rear++），然后对rear进行赋值

取出数据时：

先判断队列是否是空？

                    当rear==front时（即上图最左边),即为空

不为空将尾指针front上移，即进行front++操作

三、代码实现

java 1 private int Maxsize; 2 private int[] arr; 3 private int front; 4 private int rear; 5 //构建函数 6 public ArrayQueue(int arrMaxsize){ 7 Maxsize=arrMaxsize; 8 arr=new int[Maxsize]; 9 front=-1; 10 rear=-1; 11 } 12 //判断数组是否时空 13 public boolean isEmpty(){ 14 return front==rear; 15 } 16 17 //判断数组是否是满的 18 public boolean isFull(){ 19 return rear==Maxsize-1; 20 } 21 22 //为数组添加数据 23 public void add(int n){ 24 if (isFull()){ 25 System.out.println("数组已经满了"); 26 return; 27 } 28 rear++; 29 arr[rear]=n; 30 } 31 //删除数组数据 32 public int remove(){ 33 if (isEmpty()){ 34 new RuntimeException("数组是空的"); 35 } 36 front++; 37 return arr[front]; 38 } 39 40 //获取头数据 41 public int getHeadDate(){ 42 if (isEmpty()){ 43 new RuntimeException("数组是空的"); 44 } 45 46 return arr[front+1]; 47 } 48 //显示所有数据 49 public void allDate(){ 50 if (isEmpty()){ 51 new RuntimeException("数组是空的"); 52 } 53 for (int i=0;i<Maxsize;i++){ 54 System.out.printf("arr[%d]=%d\n",i,arr[i]); 55 } 56 57 }

 

四、优化

根据上面的代码发现，数组只能使用一次，取出数据后的空位置也不能进行添加，需要引入循环队列来解决问题

 

预留一个位置判断队列是否满：

 

 

 当取出一个后发现队列没满，可以继续添加：

 

 

 代码实现

1 private int Maxsize; 2 private int arr[]; 3 private int front;//默认是0 4 private int rear;//默认是0 5 6 //构建函数 7 public CircleArray(int arrMaxsize){ 8 Maxsize=arrMaxsize; 9 arr=new int[Maxsize]; 10 } 11 //判断数组是否时空 12 public boolean isEmpty(){ 13 return rear==front; 14 } 15 16 //判断数组是否是满的 17 public boolean isFull(){ 18 return (rear+1)%Maxsize==front; 19 } 20 21 //为数组添加数据 22 public void add(int n){ 23 if (isFull()){ 24 System.out.println("数组已经满了"); 25 return; 26 } 27 arr[rear]=n; 28 rear=(rear+1)%Maxsize; 29 } 30 //删除数组数据 31 public int remove(){ 32 if (isEmpty()){ 33 new RuntimeException("数组是空的"); 34 } 35 //先把数据值给一个局部变量 36 int a=arr[front]; 37 front=(front+1)%Maxsize; 38 return a; 39 } 40 41 //获取头数据 42 public int getHeadDate(){ 43 if (isEmpty()){ 44 new RuntimeException("数组是空的"); 45 } 46 47 return arr[front]; 48 } 49 //显示所有数据 50 public void allDate(){ 51 if (isEmpty()){ 52 new RuntimeException("数组是空的"); 53 } 54 55 for (int i=front;i<front+size();i++){ 56 System.out.printf("arr[%d]=%d\n",i%Maxsize,arr[i%Maxsize]); 57 } 58 59 } 60 61 //有效数据长度,(Maxsize-front+rear)%Maxsize 当rear<front时，长度是(maxsize-front)+(rear-0) 62 public int size(){ 63 if (isEmpty()){ 64 return 0; 65 } 66 return (Maxsize-front+rear)%Maxsize; 67 }

 

转载于:https://www.cnblogs.com/han200113/p/11526956.html