本教程的内容基本来自于《Java数据结构与算法》
队列是一种先进先出的数据结构,如下图。
每次进来新的元素,总是在队列的尾部插入;每次取出队列元素,总是在头部。队列的结构来自于生活中的排队机制。插入元素称为入队,取出元素称为出队。
使用数组实现队列,需要两个指针,一个队尾指针,一个队头指针。
1.初始化队列
class Queue{
private int rear; //队尾指针
private int front; //队头指针
private int maxSize; //队列最大存储
private int nItems; //队列中的元素个数
int[] arr;
Queue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
rear = -1;
front = 0;
nItems = 0;
}
}
2.队列是否满了
public boolean isFull(){ //判断队列是否满了
return nItems==maxSize;
}
3.队列是否为空
public boolean isEmpty(){ //判断队列是否为空
return nItems==0;
}
4.入队
public void insert(int key){ //元素入队
if (rear == maxSize-1)
rear = -1;
arr[++rear] = key;
nItems++;
}
5.出队
public int remove(){ //元素出队
int temp = arr[front++];
if (front==maxSize)
front = 0;
nItems--;
return temp;
}
6.查看队头元素
public int frontPeek(){ //查看队头元素
return arr[front];
}
7.查看队列存储的元素个数
public int size(){ //查看队列真实大小
return nItems;
}
github完整代码:
https://github.com/gamersover/data_structure_java/blob/master/Queue/QueueApp.java