什么是队列?
队列是一种线性数据结构,队列中的元素只能先进先出;
队列的出口端叫做队头,入口端叫做队尾。
队列的基本操作
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(); }}