队列数组实现-环形队列-创新互联
1.队列数组实现
网站标题:队列数组实现-环形队列-创新互联
浏览路径:http://pwwzsj.com/article/iieop.html
队列:有序列表,可以用数组和链表实现,先进先出原则,
目前累计服务客户上千家,积累了丰富的产品开发及服务经验。以网站设计水平和技术实力,树立企业形象,为客户提供成都网站制作、成都做网站、外贸营销网站建设、网站策划、网页设计、网络营销、VI设计、网站改版、漏洞修补等服务。创新互联始终以务实、诚信为根本,不断创新和提高建站品质,通过对领先技术的掌握、对创意设计的研究、对客户形象的视觉传递、对应用系统的结合,为客户提供更好的一站式互联网解决方案,携手广大客户,共同发展进步。尾部加数据(要判断队列是否满),队首取数据
1.front
含义,指向队首数据的前一个位置;
front的初始值=-1
2.rear
含义,指向队尾数据位置;
rear初始值=-1
3.队列满是rear == maxSize-1
4.队列空是front==rear
5.有效个数是rear-front
代码实现:
1.队列类public class ArrayQueue {// 使用数组模拟队列
private int maxSize;//数组的大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//存放数据,模拟队列
public ArrayQueue(int arrMaxSize) {this.maxSize=arrMaxSize;
arr = new int[maxSize];
front = -1;//指向队列头的前一个位置
rear = -1;//指向队列尾的位置
}
// 判断队列是否满
public boolean isFull(){return rear==maxSize-1;
}
// 判断队列是否为空
public boolean isEmety(){return rear==front;
}
// 添加数据到队列中
public void addQueue(int ele){if (!isFull()){arr[++rear]=ele;
return;
}else {System.out.println("队列已满");
}
}
// 取出队列的数据
public int getQueue(){if (isEmety()){throw new RuntimeException("没有数据,无法取出");
}
return arr[++front];
}
// 获取队首数据,不取出
public int headQueue(){if (isEmety()){throw new RuntimeException("没有数据,无法取出");
}
return arr[front+1];
}
// 显示队列所有数据
public void allQueue(){if (isEmety()){System.out.println("没有数据,无法取出");
return;
}
for (int i = front+1; i< rear+1; i++) {System.out.println(arr[i]);
}
}
}
2.测试队列public class ArrayQueueDemo {public static void main(String[] args) {ArrayQueue arrayQueue = new ArrayQueue(3);
boolean flag = true;
Scanner sc = new Scanner(System.in);
while (flag){System.out.println("s(show):显示队列中的全部数据");
System.out.println("h(head):获取队列中队首数据");
System.out.println("a(add):向队列添加一个数据");
System.out.println("g(get):取出队列中的一个元素");
System.out.println("e(exit):退出程序");
System.out.print("请输入操作:");
char c = sc.next().charAt(0);
switch (c){case 's':
arrayQueue.allQueue();
break;
case 'h':
try {int i = arrayQueue.headQueue();
System.out.println("队首的数据是:"+i);
} catch (Exception e) {System.out.println(e.getMessage());
}
break;
case 'a':
System.out.print("请输入要添加的数据:");
int add = sc.nextInt();
arrayQueue.addQueue(add);
break;
case 'g':
try {int get = arrayQueue.getQueue();
System.out.println("取出的数据是:"+get);
} catch (Exception e) {System.out.println(e.getMessage());
}
break;
case 'e':
sc.close();
flag = false;
break;
default:
System.out.println("输入错误");
break;
}
}
System.out.println("程序退出!");
}
}
3.问题分析:(环形队列可复用)1.目前数组只能使用一次,没有达到复用的效果,将这个数组用一个算法,改进为环形队列(取模);
1.解决:使用数组模拟环形队列1.front
含义改变,由指向队首数据的前一个位置,变成队首数据位置
front的初始值=0
2.rear
含义改变,由指向队尾数据位置,变成队尾数据的后一个位置
rear初始值=0
空出一个空间作为约定;
3.队列满是由rear == maxSize-1
变成(rear+1)%maxSize==front
;
4.队列空不改变,还是front==rear
5.有效个数是(rear+max-front)%max
public class CircleArrayQueue {private int[] arr;
private int front;
private int rear;
private int maxSize;
public CircleArrayQueue(int maxSize) {this.maxSize = maxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
public boolean isFull(){return (rear+1)%maxSize==front;
}
public boolean isEmepty(){return rear==front;
}
//队列添加元素
public void addQueue(int ele){if (isFull()){System.out.println("队列满了,无法添加元素");
return;
}
arr[rear]=ele;
rear=(rear+1)%maxSize;
}
//取出队首元素
public int getQueue(){if (isEmepty()){throw new RuntimeException("队列没有元素,无法取出数据");
}
int a = arr[front];
arr[front]=0;
front = (front+1) % maxSize;
return a;
}
//显示队首元素
public int headQueue(){if (isEmepty()){throw new RuntimeException("队列没有元素,无法取出数据");
}
return arr[front];
}
//显示队列所有数据
public void allQueue(){if (isEmepty()){System.out.println("没有数据");
return;
}
int count = size();
for (int i = front; i< front+count; i++) {System.out.println(arr[i%maxSize]);
}
}
//有效数据个数
public int size(){return (rear+maxSize-front)%maxSize;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站标题:队列数组实现-环形队列-创新互联
浏览路径:http://pwwzsj.com/article/iieop.html