什么是队列？
队列是一种线性数据结构,队列中的元素只能先进先出；
队列的出口端叫做队头,入口端叫做队尾。
队列的基本操作
1.入队:
-
只允许在队尾的位置放入元素,新元素的下一个位置将会成为新的队尾;
public void enQueue(int element) throws Exception{
if((rear+1)%array.length==front){
throw new Exception("队满!!!");
}
array[rear]=element;
rear=(rear+1)%array.length;
}
2.出队:
-
类似于入队,只允许在对头的位置移除元素,出队元素的后一个元素将会成为新的对头; -
当一个队列经过反复的入队和出队操作,还剩下2个元素,这时又有新元素入队时,在数组不扩容的 -
情况下,将队尾指针重新指向数组的首位，实现循环队列的数据结构。
public int deQueue() throws Exception{
if(front==rear){
throw new Exception("队满!!!");
}
int deElement=array[front];
front=(front+1)%array.length;
return deElement;
}
3.判断队满的情况:
-
当(队尾下标+1)%数组长度=队头下标时,队满; -
队尾指针指向的位置永远空出一位,所以队列最大容量比数组长度小1。
完整代码
点击查看代码
package Queue;
public class MyQueue {
//定义数组
private int[] array;
//对头指针
private int front;
//队尾指针
private int rear;
//定义队列的构造方法(类似数组)
public MyQueue(int capacity){
this.array=new int[capacity];
}
//入队操作(element:入队元素)
public void enQueue(int element) throws Exception{
if((rear+1)%array.length==front){
throw new Exception("队满!!!");
}
array[rear]=element;
rear=(rear+1)%array.length;
}
//出队操作
public int deQueue() throws Exception{
if(front==rear){
throw new Exception("队满!!!");
}
int deElement=array[front];
front=(front+1)%array.length;
return deElement;
}
//输出队列
public void output(){
for(int i=front;i!=rear;i=(i+1)%array.length){
System.out.print(array[i]+" ");
}
}
public static void main(String[] args) throws Exception{
MyQueue myQueue=new MyQueue(6);
myQueue.enQueue(1);
myQueue.enQueue(2);
myQueue.enQueue(3);
myQueue.enQueue(4);
myQueue.enQueue(5);
myQueue.deQueue();
myQueue.deQueue();
myQueue.enQueue(6);
myQueue.enQueue(7);
myQueue.output();
}
}