（所有源码均在 https://github.com/zongzhec/AlgoPractise）
概述
首先，如果用数组模拟队列，至少需要两个指针——front 和 rear，算了，就叫start （后称S）和 end （后称E）吧。
S代表当前有效数据的头部，E代表尾部。（因为队列中的数据会被取出，所以显然头部不可能总是0）。
要素分析
虽然我们会遇到以下几种情况的搭配组合，但是他们在实现的逻辑上是等价的。
- S可以表示为头元素的前一个位置（初始值为-1）；
- S也可以表示头元素当前位置（初始值为0）；
- E可以表示末元素的位置；
- E也可以表示为末元素位置+1。
既然等价，那就先随便挑一个组合：S表示头元素当前位置，E表示为末元素位置+1。
这样可以比较容易的理解为：S直接代表取元素时候的位置，E代表放元素时候的位置。
源码
如果不考虑其他因素，码出来的源码差不多是这样的。（其他没列出的源码均在 https://github.com/zongzhec/AlgoPractise）
-
package foo.zongzhe.line.queue;
-
-
/**
-
* 用数组实现循环队列思路1：
-
* start为头元素所在位置，end为末元素所在位置+1
-
*/
-
public
class ArrayQueueCircle1 extends ArrayQueue {
-
-
/**
-
* 创建队列构造器
-
*/
-
public ArrayQueueCircle1(int queueSize) {
-
super(queueSize);
-
this.maxSize = queueSize;
-
array =
new
int[maxSize];
-
start = -
1;
// 指向队列头部
-
end =
0;
-
arrayQueueDesc =
"ArrayQueueCircle1";
-
System.out.println(String.format(
"%s initialized. start = %d, end = %d", arrayQueueDesc, start, end));
-
}
-
-
/**
-
* 判断队列是否满
-
*/
-
@Override
-
public boolean isFull() {
-
return start == end;
-
}
-
-
/**
-
* 判断队列是否为空
-
*
-
* @return boolean 队列是否为空
-
*/
-
@Override
-
public boolean isEmpty() {
-
return start == end -
1;
-
}
-
-
/**
-
* 添加数据到队列
-
*
-
* @param element 数据
-
*/
-
@Override
-
public void addElement(int element) {
-
if (isFull()) {
-
System.out.println(String.format(
"%s is full, no values are allowed to add", arrayQueueDesc));
-
}
else {
-
// start = (start == -1)? 0: start;
-
array[end] = element;
-
end = (end +
1) % maxSize;
-
System.out.println(String.format(
"%s added one element %d. start = %d, end = %d", arrayQueueDesc, element, start, end));
-
}
-
}
-
-
/**
-
* 从队列中取出元素
-
*
-
* @return 元素的值
-
*/
-
@Override
-
public int takeElement() {
-
if (isEmpty()) {
-
throw
new RuntimeException(String.format(
"%s is empty, no values are able to retrieve", arrayQueueDesc));
-
}
else {
-
int res = array[start];
-
start = (start +
1) % maxSize;
-
return res;
-
}
-
}
-
-
/**
-
* 遍历队列
-
*/
-
@Override
-
public void showElements() {
-
if (isEmpty()) {
-
System.out.println(String.format(
"%s is empty, no values are able to show", arrayQueueDesc));
-
}
else {
-
System.out.print(
"Iterating " + arrayQueueDesc +
": ");
-
for (
int i = start; i < end; i = (i +
1) % maxSize) {
-
System.out.print(array[i] +
" ");
-
}
-
System.out.println();
-
}
-
}
-
-
}
我们再写一个Demo类来测试：
-
package foo.zongzhe.line.queue;
-
-
import java.util.ArrayList;
-
-
/**
-
* 使用多种方法数组来模拟队列，包括环形和非环形。
-
*/
-
-
public
class ArrayQueueDemo {
-
-
static ArrayList<ArrayQueue> arrayQueues;
-
-
public static void main(String[] args) {
-
-
// 创建队列
-
int queueSize =
5;
-
initialArrayQueues(queueSize);
-
-
// 判断是否为空
-
checkIsEmpty();
-
-
// 添加一个元素
-
int[] values = {
3};
-
addElements(values);
-
showElements();
-
-
// 再次判断是否为空
-
checkIsEmpty();
-
-
// 连续添加多个元素直至满元素
-
int[] values2 = {
5,
2,
4,
5};
-
addElements(values2);
-
showElements();
-
-
// 判断队列是否满了
-
checkIsFull();
-
-
// 取出多个元素
-
takeElement(
2);
-
-
// 再次添加一个元素，查看队列是否可以循环利用
-
int[] values3 = {
3};
-
addElements(values3);
-
-
// 再次判断队列是否满了
-
checkIsFull();
-
-
// 展示全部元素
-
showElements();
-
-
}
-
-
-
private static void initialArrayQueues(int queueSize) {
-
arrayQueues =
new ArrayList<>();
-
// arrayQueues.add(new ArrayQueueNoCircle(queueSize)); // 加一个ArrayQueueNoCircle
-
arrayQueues.add(
new ArrayQueueCircle1(queueSize));
// 加一个ArrayQueueCircle1
-
}
-
-
private static void checkIsEmpty() {
-
for (ArrayQueue arrayQueue : arrayQueues) {
-
System.out.println(String.format(
"%s isEmpty? %b", arrayQueue.arrayQueueDesc, arrayQueue.isEmpty()));
-
}
-
-
}
-
-
private static void addElements(int[] elementValues) {
-
for (ArrayQueue arrayQueue : arrayQueues) {
-
for (
int elementValue : elementValues) {
-
arrayQueue.addElement(elementValue);
-
}
-
}
-
}
-
-
private static void checkIsFull() {
-
for (ArrayQueue arrayQueue : arrayQueues) {
-
System.out.println(String.format(
"%s isFull? %b", arrayQueue.arrayQueueDesc, arrayQueue.isFull()));
-
}
-
}
-
-
private static void takeElement(int elementNumber) {
-
for (ArrayQueue arrayQueue : arrayQueues) {
-
for (
int i =
1; i <= elementNumber; i++) {
-
int res = arrayQueue.takeElement();
-
}
-
}
-
}
-
-
private static void showElements() {
-
for (ArrayQueue arrayQueue : arrayQueues) {
-
arrayQueue.showElements();
-
}
-
-
}
-
-
}
运行结果和思考
一旦运行，发现程序报错了，说是取元素的下标越界。
不难理解，因为我么初始化的时候S=-1，但是取元素时候显然是没有-1这个下标的。
怎么办？一个明显的思路就是但凡我在队列里面添加了第一个元素，我就立即把S重制成0。
-
/**
-
* 添加数据到队列
-
*
-
* @param element 数据
-
*/
-
@Override
-
public void addElement(int element) {
-
if (isFull()) {
-
System.out.println(String.format(
"%s is full, no values are allowed to add", arrayQueueDesc));
-
}
else {
-
start = (start == -
1)?
0: start;
// 重置S的值，以免下标为-1，造成越界
-
array[end] = element;
-
end = (end +
1) % maxSize;
-
System.out.println(String.format(
"%s added one element %d. start = %d, end = %d", arrayQueueDesc, element, start, end));
-
}
-
}
再跑一把，发现是另外一个Exception：明明有数据，但是取数据的时候说队列为空，无法取数据。
为什么呢？因为在判断队列是否为空的时候，我们检查的是S是否等于E。
-
/**
-
* 判断队列是否为空
-
*
-
* @return boolean 队列是否为空
-
*/
-
@Override
-
public boolean isEmpty() {
-
return start == end;
-
}
这里就遇到了一个问题：怎么判定队列为空？！
- 如果有1个元素，那么S = E - 1，因为S表示头元素当前位置，E表示为末元素位置+1；
- 如果有2个元素，那么S = E - 2；
- 如果有3个元素，那么S = E - 3；
- ……
- 如果有maxSize - 1个元素，那么考虑到回环的可能，S = E - (maxSize - 1)，即S = (E+1)%maxSize；
- 如果有maxSize个元素（满元素），那么S = E - maxSize，即S = E%maxSize；
如果你还没有明白问题在哪里，那我举个例子：假设这个队列的容量是5，经过一系列操作后，从位置3开始再次挨个儿插入元素。
你会发现，E已经把所有能遍历的位置都使用完了，而这里面没有适用于“查看队列是否为空”的情形！
咋办？……
那我们就必须使其中一个情形让出位置，来标记“队列为空”的情形，从逻辑上来说，只能放弃“有5个元素”的情况。（因为一旦可以检查是否有5各元素，就必定可以检查是否有4,3,2,1个元素的情形，那每个都不可以放弃）
思路改进
放弃了“有5个元素”的情况，那说明我们这个maxSize为5的数组就不能当做一个size为5的队列，那只能要求数组在实现循环队列的时候，队列的size等于数组size-1。
判断队列是否为空的条件就可以写S是否等于E。
判断队列是否满了的条件就可以写S是否等于E+1。
代码改进
有了上述设计，代码只需要细微的调整。
-
package foo.zongzhe.line.queue;
-
-
/**
-
* 用数组实现循环队列思路1：
-
* start为头元素所在位置，end为末元素所在位置+1
-
* 数组的size = 队列的size+1
-
*/
-
public
class ArrayQueueCircle1 extends ArrayQueue {
-
-
/**
-
* 创建队列构造器
-
*/
-
public ArrayQueueCircle1(int queueSize) {
-
super(queueSize);
-
this.arraySize = queueSize +
1;
-
array =
new
int[arraySize];
-
start =
0;
// 指向队列头部
-
end =
0;
-
arrayQueueDesc =
"ArrayQueueCircle1";
-
System.out.println(String.format(
"%s initialized. start = %d, end = %d", arrayQueueDesc, start, end));
-
}
-
-
/**
-
* 判断队列是否满
-
*/
-
@Override
-
public boolean isFull() {
-
return start == (end +
1) % arraySize;
-
}
-
-
/**
-
* 判断队列是否为空
-
*
-
* @return boolean 队列是否为空
-
*/
-
@Override
-
public boolean isEmpty() {
-
return start == end;
-
}
-
-
/**
-
* 添加数据到队列
-
*
-
* @param element 数据
-
*/
-
@Override
-
public void addElement(int element) {
-
if (isFull()) {
-
System.out.println(String.format(
"%s is full, no values are allowed to add", arrayQueueDesc));
-
}
else {
-
array[end] = element;
-
end = (end +
1) % arraySize;
-
System.out.println(String.format(
"%s added one element %d. start = %d, end = %d", arrayQueueDesc, element, start, end));
-
}
-
}
-
-
/**
-
* 从队列中取出元素
-
*
-
* @return 元素的值
-
*/
-
@Override
-
public int takeElement() {
-
if (isEmpty()) {
-
throw
new RuntimeException(String.format(
"%s is empty, no values are able to retrieve", arrayQueueDesc));
-
}
else {
-
int res = array[start];
-
start = (start +
1) % arraySize;
-
System.out.println(String.format(
"%s took one element %d. start = %d, end = %d", arrayQueueDesc, res, start, end));
-
return res;
-
}
-
}
-
-
/**
-
* 遍历队列
-
*/
-
@Override
-
public void showElements() {
-
if (isEmpty()) {
-
System.out.println(String.format(
"%s is empty, no values are able to show", arrayQueueDesc));
-
}
else {
-
System.out.print(
"Iterating " + arrayQueueDesc +
": ");
-
for (
int i = start; i != end; i = (i +
1) % arraySize) {
-
System.out.print(array[i] +
" ");
-
}
-
System.out.println();
-
}
-
}
-
-
}
运行及输出
改进之后，运行ArrayQueueDemo就没有任何问题了，输出如下：
-
> Task :ArrayQueueDemo.main()
-
ArrayQueueCircle1 initialized. start =
0,
end =
0
-
ArrayQueueCircle1
isEmpty?
true
-
ArrayQueueCircle1 added one element
3. start =
0,
end =
1
-
Iterating ArrayQueueCircle1:
3
-
ArrayQueueCircle1
isEmpty?
false
-
ArrayQueueCircle1 added one element
5. start =
0,
end =
2
-
ArrayQueueCircle1 added one element
2. start =
0,
end =
3
-
ArrayQueueCircle1 added one element
4. start =
0,
end =
4
-
ArrayQueueCircle1 added one element
5. start =
0,
end =
5
-
Iterating ArrayQueueCircle1:
3
5
2
4
5
-
ArrayQueueCircle1 isFull?
true
-
ArrayQueueCircle1 took one element
3. start =
1,
end =
5
-
ArrayQueueCircle1 took one element
5. start =
2,
end =
5
-
ArrayQueueCircle1 added one element
3. start =
2,
end =
0
-
ArrayQueueCircle1 isFull?
false
-
Iterating ArrayQueueCircle1:
2
4
5
3
转载：https://blog.csdn.net/zongziczz/article/details/105921622
查看评论