代码
public class Main {
public static void main(String[] args) {
CircleQueue circleQueue = new CircleQueue(4);
System.out.println("队列是否为空:"+ circleQueue.isEmpty());
circleQueue.addItem(1);
circleQueue.addItem(9);
circleQueue.addItem(13);
System.out.println("队列是否为空:"+ circleQueue.isEmpty());
System.out.println("队列是否已满:"+ circleQueue.isFull());
System.out.println("队列中有效数据的个数为:"+ circleQueue.itemNums());
//显示所有元素
circleQueue.showAllItems();
//取出第一个元素
int oneItem = circleQueue.getItem();
System.out.println("取出第一个元素为:" + oneItem);
//显示所有元素
circleQueue.showAllItems();
System.out.println("队列中有效数据的个数为:"+ circleQueue.itemNums());
}
}
//用数组模拟环形队列,要预留出一个空位置(这个空位置不一定是最上面的)
//当head赶上rear,队列空
//当rear赶上head,队列满
class CircleQueue{
//front指向第一个元素
int front;
//rear指向最后一个元素的下一个
int rear;
int maxSize;
int[] array;
//构造方法
CircleQueue(int maxSize){
this.maxSize = maxSize;
front = 0;
rear = 0;
array = new int[maxSize];
}
//判断是否已满
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
public boolean isEmpty(){
return rear == front;
}
//队列中有效数据的个数
public int itemNums(){
return (rear - front + maxSize) % maxSize;
}
//向队列中添加元素
public void addItem(int a){
if (isFull()){
System.out.println("队列已满 无法添加元素");
return;
}
array[rear] = a;
rear = (rear + 1) % maxSize;
}
//取出队列中第一个元素
public int getItem(){
if (isEmpty()){
throw new RuntimeException("队列是空的 没法取出了");
}
int item = array[front];
front = (front + 1) % maxSize;
return item;
}
//显示队列中的所有元素
public void showAllItems(){
if (isEmpty()){
throw new RuntimeException("队列是空的 没法取出了");
}
System.out.println("接下来显示所有元素");
int count = 0;
for (int i = front;i < front + itemNums();i++){
count++;
System.out.println("第" + count + "个元素为" + array[i]);
}
}
}
当时没想通的点:
预留的一个空位,并不一定是最上面的,而是front
和rear
之间的。
比如这个
需要记住的点
判断队列是否已满
(rear+1) % maxSize == front
判断队列是否为空
rear == front
队列有效数据的个数
(rear + maxSize - front) % maxSize