欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JAVA数据结构与算法之数组模拟环形队列

程序员文章站 2022-06-06 20:45:17
...
  • 前言:
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率

环形队列

队列简介:

详见另一篇文章 —— 数组模拟队列

环形队列的存储结构:

  • 顺序存储:
    利用一组连续的地质单元存放队列元素(通常使用数组
    JAVA数据结构与算法之数组模拟环形队列
    JAVA数据结构与算法之数组模拟环形队列

(注:因数组模拟队列,为了方便起见出入队只将两个指针进行移动)

  • 链式存储:

后续更新

队列基本操作:

  • 两个指针看作计数器,数据在核心数组中的实际位置应为指针计数的取模。
  • 为了思路清晰,我们做出如下约定:
  1. front:指向队列头
  2. rear:指向队尾后一个元素
  3. 两个指针初始值均为0

JAVA数据结构与算法之数组模拟环形队列

  • 入队(增): 将数据放入队尾(rear),并将队尾指针后移一位
  • 出队(删):队首(front) 数据取出,并将队首指针后移一位
  • 查询队首元素(查): 返回队首元素的值,并不移动指针
  • 判断队列是否为空: 判断队列中是否含有数据
  • 判断队列是否已满: 判断队列是否满

代码实现以及思路:

  • 准备工作:
  • 数据在数组中的实际存储位置应为 指针计数器1 的模
  • 对程序中用到的变量做出如下约定:
  1. front:指向队列头
  2. rear:指向队尾后一个元素
  3. 两个指针初始值均为0
	private int maxSize; // 最大容量
	private int front; // 头
	private int rear; // 尾
	private int[] data; // 核心数组

	public ArrayCircularQueue(int maxSize) {
		this.maxSize = maxSize;
		this.data = new int[maxSize];
		this.front = 0;
		this.rear = 0;
	}
  • 判空:
  1. 本身未插入数据,即 rear=front=0
  2. 插入数据后又将数据全部取出,已经取走队尾的数据,即 rear==front
	/**
	 * <pre>
	 * 判断队列是否为空
	 * </pre>
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return rear == front;
	}
  • 判满:

存储的数据已经放满整个数组,即队尾指针应比队首指针大整整一个队列的长度

  1. rear > maxSize
  2. (rear) % maxSize == front
	/**
	 * 判断队列是否已满
	 * 
	 * @return
	 */
	public boolean isFull() {
		/**
		 * <pre>
		 * 如果<code>return (rear+1) % maxSize == front</code>则空出数组最后一个位置作为约定
		 * </pre>
		 */
		return rear > maxSize && (rear) % maxSize == front;
	}
  • 入队(增):
  1. 先判断队列是否已满
  2. 将数据写在当前队尾的位置
    (1)先将数据写入队尾指针所在位置
    (2)再将队尾指针后移
	/**
	 * <pre>
	 * 向队列中增加数据
	 * </pre>
	 * 
	 * @param n 插入数据
	 * @see ArrayCircularQueue#isFull()
	 */
	public void add(int n) {
		// 判断队列是否已满
		if (isFull())
			throw new ArrayIndexOutOfBoundsException("队列已满");
		/**
		 * 等同于<code> data[rear%maxSize]=n; rear++;</code>
		 */
		data[(rear++)%maxSize] = n;
	}
  • 出队(删):
  1. 先判断队列是否为空
  2. 取出队首位置元素,并将队首指针后移
    (1)先取出front指针对应位置的元素
    (2)再将将front后移
	/**
	 * <pre>
	 * 取数据
	 * </pre>
	 * 
	 * @return
	 * @see ArrayCircularQueue#isEmpty()
	 */
	public int get() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		/**
		 * 等同于<code> return data[front%maxSize]; front++;</code>
		 */
		return data[(front++) % maxSize];
	}
  • 查询队首元素:

思路与出队基本相同,但是不将队首指针后移
因此只需取出front指针对应位置上的元素

	/**
	 * <pre>
	 * 读取队头数据
	 * </pre>
	 * 
	 * @return
	 * @see ArrayCircularQueue#isEmpty()
	 */
	public int read() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		return data[(front) % maxSize];
	}
  • 打印队列:
  1. 首先判断队列是否为空
  2. 遍历核心数组
    但是因为在做出队时只是将front后移,并没有真正的删除
    因此在遍历时,应从front指针对应的的位置开始,到rear指针对应的的位置结束
	/**
	 * <pre>
	 * 打印数据
	 * </pre>
	 * 
	 * {@link ArrayCircularQueue#isEmpty()}
	 */
	public void display() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		for (int i = front; i < rear; i++) {
			System.out.print(data[i % maxSize] + " ");
		}
		System.out.println();
	}

完整代码:

package DataStructures.linear.queue;

/**
 * 
 * <pre>
 * 数组实现环形队列
 * </pre>
 * 
 * @param <code>int   maxSize</code>->最大容量
 * @param <code>int   front</code>->指向队列头
 * @param <code>int   rear</code>->指向队列尾后一个位置
 * @param <code>int[] data</code>->核心数组
 * 
 * @author Lansion
 * @version 1.0
 * @since 1.0
 */
class ArrayCircularQueue {

	private int maxSize; // 最大容量
	private int front; // 头
	private int rear; // 尾
	private int[] data; // 核心数组

	public ArrayCircularQueue(int maxSize) {
		this.maxSize = maxSize;
		this.data = new int[maxSize];
		this.front = 0;
		this.rear = 0;
	}
	
	/**
	 * 判断队列是否已满
	 * 
	 * @return
	 */
	public boolean isFull() {
		/**
		 * <pre>
		 * 如果<code>return (rear+1) % maxSize == front</code>则空出数组最后一个位置作为约定
		 * </pre>
		 */
		return rear > maxSize && (rear) % maxSize == front;
	}

	/**
	 * <pre>
	 * 判断队列是否为空
	 * </pre>
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return rear == front;
	}
	
	/**
	 * <pre>
	 * 向队列中增加数据
	 * </pre>
	 * 
	 * @param n 插入数据
	 * @see ArrayCircularQueue#isFull()
	 */
	public void add(int n) {
		// 判断队列是否已满
		if (isFull())
			throw new ArrayIndexOutOfBoundsException("队列已满");
		/**
		 * 等同于<code> data[rear%maxSize]=n; rear++;</code>
		 */
		data[(rear++)%maxSize] = n;
	}

	/**
	 * <pre>
	 * 取数据
	 * </pre>
	 * 
	 * @return
	 * @see ArrayCircularQueue#isEmpty()
	 */
	public int get() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		/**
		 * 等同于<code> return data[front%maxSize]; front++;</code>
		 */
		return data[(front++) % maxSize];
	}

	/**
	 * <pre>
	 * 读取队头数据
	 * </pre>
	 * 
	 * @return
	 * @see ArrayCircularQueue#isEmpty()
	 */
	public int read() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		return data[(front) % maxSize];
	}

	/**
	 * <pre>
	 * 打印数据
	 * </pre>
	 * 
	 * {@link ArrayCircularQueue#isEmpty()}
	 */
	public void display() {
		if (isEmpty())
			throw new RuntimeException("队列空");
		for (int i = front; i < rear; i++) {
			System.out.print(data[i % maxSize] + " ");
		}
		System.out.println();
	}

	public int Size() {
		return rear - front;
	}

}

  1. 在本程序中指针大小并不与队列实际存储量相比较,实际的存储位置为指针的模,所以也可看作一个计数器 ↩︎