数据结构与算法-环形队列 - Go语言中文社区

数据结构与算法-环形队列


环形队列

队列是一种常用的数据结构,这种结构保证了数据是按照“先进先出”的原则进行操作的,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。

应用场景

  • 餐厅的叫号系统

整体思路

  • 设置一个固定长度为maxSize的数组,设置一个记录数组下次插入数据的 下标rear,一个数组下次删除数据的下标front,通过每次插入删除移动一位rear或front的值

  • rear和front必须考虑取模,当rear指向数组最后一个位置继续添加时,此时认为一轮添加的循环结束,此时rear = (rear + 1) % maxSize;当front指向数组最后一个位置继续获取数据时,此时认为一轮获取的循环结束,此时front = (front + 1) % maxSize;

  • 设置一个判断rear和front是否为同一轮的标记flag,同一轮为true,不是同一轮为false

  • 图解
    在这里插入图片描述
    代码思路分析

  • front:front的初始值为0,指向队列将要取出数据的位置

  • rear:rear初始值为0,指向队列将要添加数据的位置

  • maxSize :数组的长度

  • flag:初始值为true,添加数据和获取数据在同一次循环中,此时rear>=front,当rear执行完一轮之后将flag设置为false,此时rear<=front,当获取完一次完整的数据后,即开始第二轮循环后,front再次设置为0,同时设置flag为false

  • 只有当rear == front时,队列添加和获取的数组下标相同,所以此时队列为空的或者是满的,如果rear 和front是同一轮循环,说明数组是空的,否则数组是满的

  • 队列为空的条件: flag && rear == front

  • 队列满的条件: !flag && rear == front

  • 队列中有效的数据的个数 int size = flag ? rear - front : rear + maxSize - front

  • 代码实现

public static void main(String[] args) {
		
	System.out.println("数组模拟环形队列:");
	CircleArrayQueue arrayQueue = new CircleArrayQueue(4);
	char key = ' '; //接收用户输入
	Scanner scanner = new Scanner(System.in);
	boolean loop = true;
	//输出一个菜单
	while (loop) {
		System.out.println("s(show): 显示队列");
		System.out.println("e(exit): 退出程序");
		System.out.println("a(add):  添加数据到队列");
		System.out.println("g(get):  从队列里取出数据");
		System.out.println("h(head): 查看队列头数据");
		key = scanner.next().charAt(0);  //接收一个字符
		
		switch (key) {
		case 's':
			arrayQueue.showQueue();
			break;
		case 'e':
			loop = false;
			scanner.close();
			System.out.println("程序退出!");
			break;
		case 'a':
			System.out.println("输入一个数");
			int value = scanner.nextInt();
			arrayQueue.addQueue(value);
			break;
		case 'g':
			int res = arrayQueue.getQueue();
			System.out.println("取出的数据是: " + res);
			break;
		case 'h':
			int head = arrayQueue.heanQueue();
			System.out.println("第一个数据是: " + head);
			break;
		default:
			break;
		}
		System.out.println();
	}
}

class CircleArrayQueue {
	private int maxSize;  //表示数组最大容量
	private int front;  //front变量指向队列的第一个元素,front的初始值为0
	private int rear;  //rear变量指向队列的最后一个元素,rear初始值为0
	private int[] arr;  //该数组用于存放数据,模拟队列
	boolean flag;  //判断标记:true则为同一轮,false则开始了新的一轮循环
	
	//创建队列构造器
	public CircleArrayQueue(int arrayMaxSize) {
		maxSize = arrayMaxSize;
		arr = new int[arrayMaxSize];
		front = 0;  //指向队列将要取出数据的位置
		rear = 0;  //指向队列将要添加数据的位置
		flag = true;  //标记为true,用来判断rear和front是不是在同一轮中,即rear是否开始了下一轮的循环添加
	}
	
	/**
	 * 判断队列是否满
	 */
	public boolean isFull() {
		/*
		 * 当flag为false时说明下一次添加数据将会是下一轮循环,当rear和front一样时,
		 * 说明rear队列添加数据的位置与获取数据的位置相同,此时队列是满的
		 */
		return !flag && rear == front;
	}
	
	/**
	 * 判断队列是否为空
	 */
	public boolean isEmpty() {
		/*
		 * flag为true说明添加数据和获取数据在同一轮循环中,此时队列添加数据的位置与获取数据的位置相同
		 * 说明队列是空的
		 */
		return flag && rear == front;
	}
	
	/**
	 * 添加队列数据
	 */
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("队列满了,不能添加数据!");
			return;
		}
		//将rear后移,这里必须考虑取模
		arr[rear] = n;
		rear = (rear + 1) % maxSize;
		//若果rear取模后为0,说明队列开始了新的循环
		if (rear == 0) flag = false;
		
	}
	
	/**
	 * 获取队列的数据,出队列
	 */
	public int getQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空,不能获取数据!");
		}
		//这里需要分析出front指向队列的第一个元素
		//1.先把front对应的值保存到一个临时变量
		//2.将front后移,考虑取模
		//3.将临时保存的变量返回
		int val = arr[front];
		front = (front + 1) % maxSize;
		//如果front取模后为0,说明队列里添加和获取在同一轮循环中
		if (front ==0 ) flag = true;
		return val;
	}
	
	/**
	 * 显示队列所有数据
	 */
	public void showQueue() {
		//遍历
		if(isEmpty()) {
			System.out.println("队列是空的,没有数据!");
			return;
		}
		
		//思路,从front开始遍历
		int size = size();
		for (int i = front; i < front + size; i++) {
			System.out.print(arr[i % maxSize] + " ");
		}
	}
	
	/**
	 * 显示队列的头数据
	 */
	public int heanQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空,不能获取数据!");
		}
		return arr[front];
	}
	
	//求出当前数据有效数据个数
	public int size() {
		return flag ? rear - front : rear + maxSize - front;
	}

}

------此文章总结改造来自韩顺平老师讲解的java数据结构与算法

版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/weixin_42455070/article/details/106791642
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2021-12-11 18:06:51
  • 阅读 ( 1128 )
  • 分类:算法

0 条评论

请先 登录 后评论

官方社群

GO教程

猜你喜欢