数组构造队列
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class ArrayQueue{ private int[] arr; private int maxSize = 10; //队列容量,默认容量为10 private int front; //队头 private int rear; //队尾 public ArrayQueue(){ arr = new int[this.maxSize]; front = rear = -1; } public ArrayQueue(int maxSize){ this.maxSize = maxSize; arr = new int[this.maxSize]; front = rear = -1; } //判断队列是否已满 public Boolean isFull(){ return rear == maxSize-1; } //判断队列是否为空 public Boolean isEmpty(){ return front==rear; } //数据入队 public void enterQueue(int data){ if(isFull()) throw new RuntimeException("队列以满"); arr[++rear] = data; } //数据出队 public int getQueue(){ if (isEmpty()) throw new RuntimeException("队列为空"); return arr[++front]; } //显示队头数据 public int ShowFrontQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); return arr[front+1]; } //遍历队列 public void traverseQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); for(int i=1;front+i<=rear;i++) System.out.println(arr[front+i]); } }
复制代码
1
2
3
4在上面的队列构造中，存在一个最大的问题就是，当数据入队到数组的最大容量后，此时rear=MaxSize-1，表示队列已满。数据出队后，前面的空间（图上变黄的地方）虽然空出来了，但是依然无法插入数据进去。这样构造的队列每个空间只能利用一次。 为了达到重复利用，需要优化成循环队列，允许队头和队尾围绕一个圈移动。
优化成循环队列
构造成环形队列不唯一，可根据实际情况构造。不同的设计在计算队列是否为空，是否已满的算法上存在不同。
构造第一种环形队列
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class ArrayQueue{ private int[] arr; private int maxSize = 10; //队列容量,默认容量为10 private int front; //队头 private int rear; //队尾 public ArrayQueue(){ arr = new int[this.maxSize]; front = rear = -1; } public ArrayQueue(int maxSize){ this.maxSize = maxSize; arr = new int[this.maxSize]; front = rear = -1; } //判断队列是否已满 public Boolean isFull(){ return (rear-front)%maxSize==0&&arr[0]!=0; //值等于0表示此空间没有数据作为前提条件 } //判断队列是否为空 public Boolean isEmpty(){ return (rear-front)%maxSize==0&&arr[0]==0; } //数据入队 public void enterQueue(int data){ if(isFull()) throw new RuntimeException("队列以满"); rear = (rear+1)%maxSize; arr[rear] = data; } //数据出队 public int getQueue(){ if (isEmpty()) throw new RuntimeException("队列为空"); front = (front+1)%maxSize; //出队把数据还原成0 int temp = arr[front]; arr[front] = 0; return temp; } //显示队头数据 public int ShowFrontQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); return arr[(front+1)%maxSize]; } //遍历整个数组 public void traverseQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); for(int i=0;i<maxSize;i++) System.out.print(arr[i]+" "); } }
构造第二种环形队列
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class ArrayQueue{ private int[] arr; private int maxSize = 10; //队列容量,默认容量为10 private int front; //队头 private int rear; //队尾 public ArrayQueue(){ arr = new int[this.maxSize]; front = rear = 0; } public ArrayQueue(int maxSize){ this.maxSize = maxSize; arr = new int[this.maxSize]; front = rear = 0; } //判断队列是否已满 public Boolean isFull(){ return (rear+1)%maxSize==front; //值等于0表示此空间没有数据作为前提条件 } //判断队列是否为空 public Boolean isEmpty(){ return rear == front; } //数据入队 public void enterQueue(int data){ if(isFull()) throw new RuntimeException("队列以满"); arr[rear] = data; rear = (rear+1)%maxSize; } //数据出队 public int getQueue(){ if (isEmpty()) throw new RuntimeException("队列为空"); int temp = arr[front]; front = (front+1)%maxSize; return temp; } //显示队头数据 public int ShowFrontQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); return arr[front]; } //遍历整个数组 public void traverseQueue(){ if(isEmpty()) throw new RuntimeException("队列为空"); for(int i=0;i<maxSize;i++) System.out.print(arr[i]+" "); } }
总结
从简单的数组实现队列，到后来为了解决空间的重复利用，通过构造环形队列。在构造环形队列上：
1.没有固定写法
2.只要你设计的环形队列能够正确判断出什么情况队列满，什么情况队列空，能够重复利用空间，队头始终能表示第一个插入进来的数据
3.画图分析，总结出自己的写法。
最后
以上就是难过金针菇最近收集整理的关于数组构造队列数组构造队列优化成循环队列总结的全部内容，更多相关数组构造队列数组构造队列优化成循环队列总结内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复