队列定义
队列是一种先进先出的数据结结构。队列的使用场景
银行排队挂号等。Java用数组实现
package cn.chmcyz.queue;package cn.chmcyz.queue;/*** @author 谌涣谋* @date /5/12 - 17:00*/public class ArrayQueueDemo {public static void main(String[] args) {ArrayQueue queue=new ArrayQueue(5);queue.add(10);queue.add(20);queue.add(30);queue.add(40);queue.add(50);queue.show();queue.pop();queue.pop();queue.show();queue.add(5);//queue.peek();queue.show();}}class ArrayQueue{private int maxSize;//队列存储的最大值private int front;//头指针private int rear;//尾指针private int []arr;//该数组模拟队列public ArrayQueue(int maxSize) {this.maxSize = maxSize;arr=new int[maxSize];front=0;//指向队列头部rear=0;//指向队列尾部的后一个位置}//判断队列是否满了public boolean isFull(){if (rear==maxSize){return true;}return false;}//判断队列是否为空public boolean isEmpty(){return front==rear;}//向队列添加数据public void add(int a){if(isFull()){throw new RuntimeException("队列已满");}arr[rear]=a;rear++;//尾指针+1}//获取队列头部数据，出队列public int pop(){if(isEmpty()) {throw new RuntimeException("队列为空");}int value= arr[front];arr[front++]=0;return value;}//获取队列头部数据，不出队列public int peek(){if(isEmpty()) {throw new RuntimeException("队列为空");}return arr[front];}//显示队列所有数据public void show(){if( arr==null || arr.length==0){throw new RuntimeException("队列为空");}for (int i:arr) {if(i!=0)System.out.print(i+"\t");}System.out.println();}}
这样实现的队列有一个问题：就是不能循环使用空间：
比如上诉测试用例中，现在队列中添加元素10,20,30,40,50
再出队列一个，再往队列里面添加元素时，因为空间不足而抛出异常。
解决的方法是使用循环队列。
代码如下：
package cn.chmcyz.queue;/*** @author 谌涣谋* @date /5/12 - 18:22*/public class ArrayRoundQueueDemo {public static void main(String[] args) {ArrayRoundQueue queue=new ArrayRoundQueue(5);queue.add(10);queue.add(20);queue.add(30);queue.add(40);queue.show();queue.pop();queue.pop();queue.show();queue.add(60);queue.add(70);queue.show();}}/*** 循环队列的长度是(rear+maxSize-front)%maxSize*/class ArrayRoundQueue{private int maxSize;//队列存储的最大值private int front;//头指针private int rear;//尾指针private int []arr;//该数组模拟队列public ArrayRoundQueue(int maxSize) {this.maxSize = maxSize;arr=new int[maxSize];front=0;//指向队列头部rear=0;//指向队列尾部的后一个位置}//判断队列是否满了public boolean isFull(){if ((rear+1)%maxSize==front){return true;}return false;}//判断队列是否为空public boolean isEmpty(){return front==rear;}//向队列添加数据public void add(int a){if(isFull()){throw new RuntimeException("队列已满");}arr[rear]=a;rear=(rear+1)%maxSize;//尾指针+1}//获取队列头部数据，出队列public int pop(){if(isEmpty()) {throw new RuntimeException("队列为空");}int value= arr[front];arr[front]=0;front=(front+1)%maxSize;return value;}//获取队列头部数据，不出队列public int peek(){if(isEmpty()) {throw new RuntimeException("队列为空");}return arr[front];}//显示队列所有数据public void show(){if( arr==null || arr.length==0){throw new RuntimeException("队列为空");}for (int i=front;i<front+(rear+maxSize-front)%maxSize;i++) {System.out.print(arr[i%maxSize]+"\t");}System.out.println();}}
结果如下
