一.队列的定义
队列是指在表的一端进行插入操作,在另一端进行删除操作的一种数据结构。它是一种先进先出的线性表,就如同日常生活中排队的场景一样,最早进入队列的人最早离开。在队列中,先进入的一端称为队头(front),后进入的一端称为队尾(rear)。
二.队列的基本操作
- 初始化——构造一个空队列
- 入队——在队列的队尾插入一个新元素
- 出队——删除队列的队头元素
- 获取队头——取队列队头元素
- 求长度——求出队列中数据元素的个数
- 判空——判断当前队列是否为空
- 正序遍历——依次访问队列中每个元素并且输出
- 销毁——销毁一个已存在的队列
三.顺序队列
顺序队列可以用简单的一维数组来进行表示,此外,还可以设置两个指针front和rear分别指向队列的头部和尾部。
四.循环队列
由于使用顺序队列在进行队列的入队、出队操作是在两端进行的,随着元素的不断插入、删除,两端都向后移动,队列很快就会移动到数组的末端造成溢出,而前面的单位无法利用,就会造成资源的浪费,因此提出了循环队列。
循环队列的定义如下:
public class sequenceQueue<T>{
final int maxSize = 10;
private T queueArray[];
private int front;
private int rear;
public sequenceQueue(){} //构造一个队列
public void enQueue(T obj){} //在队列队尾插入一个新元素
public T deQueue(){} //删除队列队头元素
public T getHead(){} //取队头元素
public int size(){} //求队列中数据元素的个数
public boolean isEmpty(){} //判空
public void nextOrder(){} //遍历
public void clear(){} //销毁队列
}
1.队列的初始化
public sequenceQueue(){
front = rear = 0;
queueArray = (T[]) new Object[maxSize];
}
2.入队
public void enQueue(T obj){
if((rear+1)%queueArray.length == front){
System.out.println("error");
}
rear = (rear+1)%queueArray.length;
queueArray[rear] = obj;
}
3.出队
public T deQueue(){
if(rear = front){
System.out.println("error");
return null;
}
front = (frotn+1)%queueArray.length;
return queueArray[front];
}
4.取头元素
public T getHead(){
if(rear = front){
System.out.println("error");
return null;
}
front = (front+1)%queueArray.length;
return queueArray[front];
}
5.队列的判空
public boolean isEmpty(){
if(rear = front){
return true;
}
else{
return false;
}
}
6.队列的长度
public int size(){
return queueArray.length;
}
7.遍历队列
public void nextOrder(){
int i,j = front;
for(i=1;i<=size;i++){
j = (j+1)%queueArray.length;
System.out.println(queueArray[j]);
}
}
8.清空队列
public void clear(){
rear = front;
}