队列
程序员文章站
2022-03-05 12:40:35
...
队列介绍
- 队列是一个有序列表,可以用数组或链表来实现。
- 遵循先入先出的原则。
数组模拟队列
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的最大容量就是数组的长度。
因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下表,front会随着数据输出而改变,rear则是随着数据输入而改变。
当我们将数据存入队列时称为“addQueue”,addQueue的处理需要有两个步骤:
- 将尾指针往后移:rear+1,当front==rear 【空】
- 若尾指针rear小于队列的最大下表maxSize-1,则将数据存入rear所指的数据元素中,否则无法存入数据。rear==maxSize-1 【队列满】
代码实现
class ArrayQueue{
private int maxSize; //队列的最大容量
private int front; //队列头
private int rear; // 队列尾
private int[] arr; //模拟队列的数组,用于存数据
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[this.maxSize];
this.front = -1; //指向队列头部,指向队列头的前一个位置。
this.rear = -1; // 指向队列尾,即队列最后一个数据
}
public boolean isFull(){
return rear==this.maxSize-1;
}
public boolean isempty(){
return rear==front;
}
public void addQueue(int n){
if (isFull()){
System.out.println("队列已满");
return;
}
rear ++; //让rear后移
arr[rear] = n;
}
// 获取队列的数据,出队列
public int getQueue(){
if (isempty()){
throw new RuntimeException("队列为空");
}
front++;
return arr[front];
}
//显示队列所有数据
public void showQueue(){
if (isempty()){
System.out.println("队列为空");
return;
}
for (int i=0;i<arr.length;i++){
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
public int headQueue(){
if (isempty()){
throw new RuntimeException("队列没有数据");
}
return arr[++front];
}
}
环形队列实现
/**
* 可循环使用的数组环绕队列
* 1、front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一元素,
* front的初始值=0
* 2、rear变量的含义做一个调整,rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间做为约定
* rear的初始值=0
* 3、当队列满时,条件是:(rear+1)% maxSize == front [满]
* 4、 对队列为空的条件,rear==front 【空】
* 5、 队列中有效的数据个数 (rear + maxSize - front)%maxSize
*/
class ArrayQueue2{
private int maxSize; //队列的最大容量
private int front; //队列头
private int rear; // 队列尾
private int[] arr; //模拟队列的数组,用于存数据
public ArrayQueue2(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
}
public boolean isFull(){
return (rear+1)%maxSize==front;
}
public boolean isempty(){
return rear==front;
}
public void addQueue(int n){
if (isFull()){
System.out.println("队列已满");
return;
}
arr[rear] = n;
rear = (rear+1)%maxSize;
}
// 获取队列的数据,出队列
public int getQueue(){
if (isempty()){
throw new RuntimeException("队列为空");
}
int result = arr[front];
front = (front+1)%maxSize;
return result;
}
//显示队列所有数据
public void showQueue(){
if (isempty()){
System.out.println("队列为空");
return;
}
//获取有效个数数据
int count = size();
for (int i=front;i<front+count;i++){
System.out.printf("arr[%d]=%d\n",(i%maxSize),arr[i%maxSize]);
}
}
public int size(){
return (rear+maxSize-front) % maxSize;
}
public int headQueue(){
if (isempty()){
throw new RuntimeException("队列没有数据");
}
return arr[front];
}
}