什么是队列
- 队列是一个有序列表, 可以用数组或链表实现
- 先入先出
使用数组模拟队列和环形队列
- 用数组模拟队列
思路:
1.根据队列的最大容量创建一个数组来保存队列数据
2.定义两个变量, front和rear分别记录队列前后端的下标, 取数据front++, 存数据rear++
class ArrayQueue{
private int maxSize; //数组的最大容量
private int front; //队列头
private int rear; //队列尾
private int[] arr; //存放数据
/**
* 创建队列
* @param maxSize
*/
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
/**
* 判断队列是否已经满了
* @return
*/
public boolean isFull(){
return rear == maxSize - 1;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty(){
return rear == front;
}
/**
* 添加数据到队列
* @param n
*/
public void addQueue(int n){
if(isFull()){
System.out.println("满了");
return;
}
rear ++;
arr[rear] = n;
}
/**
* 从队列中获取数据
* @return
*/
public int getQueue(){
if(isEmpty()){
throw new RuntimeException("空");
}
front ++;
return arr[front];
}
/**
* 获取队列的第一个数据, 注意不是取数据
* @return
*/
public int headQueue(){
if(isEmpty()){
throw new RuntimeException("空");
}
return arr[front + 1];
}
/**
* 遍历队列
*/
public void showQueue(){
if(isEmpty()){
System.out.println("空队列");
return;
}
for(int i=0; i<arr.length; i++){
System.out.println(arr[i]);
}
}
}
- 使用数组模拟环形队列
为了充分利用数组，我们可以将数组看做是一个环形的
思路:
1.尾索引的下一个为头索引时表示满, 即(rear + 1)%maxSize == front
2.rear == front时, 表示空
class CircleArrayQueue{
private int maxSize; //数组的最大容量
private int front; //指向队列的第一个元素, 初始值为0
private int rear; //指向队列的最后一个元素的后一个位置, 初始值为0
private int[] arr; //存放数据
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
}
/**
* 队列是否已满
* @return
*/
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
/**
* 队列是否为空
* @return
*/
public boolean isEmpty(){
return rear == front;
}
/**
* 添加数据到队列
* @param n
*/
public void addQueue(int n){
if(isFull()){
System.out.println("满");
return;
}
//rear指向对尾下一步, 所以把插入的数组复制给arr[rear]即可
arr[rear] = n;
rear = (rear + 1) % maxSize; //rear后移
}
/**
* 出队列
* @return
*/
public int getQueue(){
if(isEmpty()){
throw new RuntimeException("空");
}
//取第一个值
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
/**
* 显示头数据
* @return
*/
public int headQueue(){
if(isEmpty()){
throw new RuntimeException("空队列");
}
return arr[front];
}
/**
* 遍历队列数据
*/
public void showQueue(){
if(isEmpty()){
System.out.println("空");
return;
}
//求队列中有效数据的个数
int size = (rear + maxSize - front) % maxSize;
for(int i=0; i<front+size; i++){
System.out.println(arr[i%maxSize]);
}
}
}
