队列介绍

  1. 队列是一个有序列表,可以用数组或是链表来实现。
  2. 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出

数组模拟队列

队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front及 rear分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear则是随着数据输入而改变,如图所示:

思路分析

  1. 将尾指针往后移:rear+1 , 当front == rear 【空】
  2. 若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear所指的数组元素中,否则无法存入数据。 rear  == maxSize – 1[队列满]

代码实现

package moti.queue;

/**
 * 数组实现队列
 * @author Moti
 * @Time 2020年2月19日 上午11:00:51
 */
public class ArrayQueue {

	public static void main(String[] args) {
		ArrQueue queue = new ArrQueue(3);
		queue.addElement(6);
		queue.addElement(8);
		queue.addElement(12);
		queue.showQueue();
		System.out.println(queue.removerElement()+"出队列");
		System.out.println("头"+queue.headQueue());
		queue.addElement(12);
	}
}

/**
 * 队列类
 * @author Moti
 * @Time 2020年2月19日 上午11:04:30
 */
class ArrQueue{
	//最大容量
	private int maxSize;
	//执行队列头
	private int front;
	//执行队列尾
	private int rear;
	//存放数据
	private int[] arr;
	
	/**
	 * 初始化队列
	 */
	public ArrQueue(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
		//指向队列头的前一个位置
		front = -1;
		//指向队列尾的位置(队列的最后一个数据)
		rear = -1;
	}
	
	/**
	 * 判断队列是否已满
	 */
	public boolean isFull() {
		return rear == maxSize -1;
	}
	
	/**
	 * 判断队列是否为空
	 */
	public boolean isEmpty() {
		return rear == front;
	}
	
	/**
	 * 添加数据
	 */
	public void addElement(int element) {
		if(isFull()) {
			System.out.println("队列已满!添加失败");
			return;
		}
		//rear后移,并赋值
		arr[++rear] = element;
	}
	
	/**
	 * 出队列
	 */
	public int removerElement() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空!移除失败");
		}
		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("队列为空!");
		}
		//front本身指向的是队列头的前一个位置
		return arr[front+1];
	}
}

数组模拟环形队列

对前面的数组模拟队列的优化,充分利用数组。因此将数组看做是一个环形的。(通过取模的方式来实现即可)

思路分析

  1. 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]
  2. rear == front [空]
  3. 队列中有效的数据的个数   (rear + maxSize – front) % maxSize

代码实现

package moti.queue;

/**
 * 数组实现队列
 * @author Moti
 * @Time 2020年2月19日 上午11:00:51
 */
public class CircleArrayQueue {

	public static void main(String[] args) {
		//MaxSize为4,但是最多有效数据为3,因为要预留一个位置形成环形队列的约定
		CircleArrQueue queue = new CircleArrQueue(4);
		queue.addElement(6);
		queue.addElement(8);
		queue.addElement(12);
		queue.showQueue();
		System.out.println(queue.removerElement()+"出队列");
		System.out.println("头"+queue.headQueue());
		queue.addElement(44);
		queue.showQueue();
	}
}

/**
 * 队列类
 * @author Moti
 * @Time 2020年2月19日 上午11:04:30
 */
class CircleArrQueue{
	//最大容量
	private int maxSize;
	//指向队列头,队列的第一个元素
	private int front;
	//指向队列尾的后一个元素(预留出一个位置)
	private int rear;
	//存放数据
	private int[] arr;
	
	/**
	 * 初始化队列
	 */
	public CircleArrQueue(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 addElement(int element) {
		if(isFull()) {
			System.out.println("队列已满!添加失败");
			return;
		}
		//直接将数据加入
		arr[rear] = element;
		//将rear后移,考虑取模
		rear = (rear + 1) % maxSize;
	}
	
	/**
	 * 出队列
	 */
	public int removerElement() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空!移除失败");
		}
		//front指向的是队列的第一个元素
		//1.将front的值保存
		int value = arr[front];
		//2.将front后移,考虑取模
		front = (front + 1) % maxSize;
		//3.返回数据
		return value;
	}
	
	/**
	 * 遍历队列
	 */
	public void showQueue() {
		if (isEmpty()) {
			System.out.println("队列为空!遍历失败");
			return;
		}
		for (int i = front; i < front+getCurCount(); i++) {
			System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
		}
	}

	/**
	 * 获取当前队列的有效个数
	 */
	public int getCurCount(){
		return  (rear + maxSize -front) % maxSize;
	}

	/**
	 * 获得队列头(并不移除)
	 */
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空!");
		}
		//front本身指向的是队列第一个位置
		return arr[front];
	}
}
最后修改日期:2020-07-12

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。