首页 > 数组模拟循环队列(Java代码)
头像
牛客775426005号
编辑于 2020-12-05 09:07
+ 关注

数组模拟循环队列(Java代码)

用数组来模拟循环队列
在循环队列中,保留一个单元。即队列中还有一个位置的时候,就默认认为队列已满
private int maxSize;// 队列容量,队列可存放数据的大小是队列容量-1
private int front;// 队列头,起始为0,表示队列第一个有值的元素的位置
private int rear;// 队列尾,起始为0,表示队列最后一个有值的元素的下一个位置
private int[] arr;// 存放数据模拟队列
    
重点理解如何判断队列满和求出当前队列有多少个元素

判断队列已满的条件
(rear + 1) % maxSize == front
可以理解成,队尾已经绕了一圈赶到了队列头的位置,则队列已满(注意保留一个空闲的位置)
建议忽略 %maxSize 来理解 即rear的下一个位置是front时,循环队列已满
取模的原因是保证队列的头和尾在这个数组的范围内

判断队列有多少个元素
(rear + maxSize - front) % maxSize
先不取模来理解,同样用上图,队列有多少个元素可以简单理解成rear-front,考虑到rear可能在front的前面,于是加上maxSize 再对整个值取模来表示当前队列有多少个元素

掌握这两个难点后即可模拟队列
完整代码如下

package com.queue;

import java.util.Scanner;

//模拟环形队列
public class CircleQueueDemo {

	public static void main(String[] args) {
		// 模拟队列的实现
		CircleQueue aq = new CircleQueue(4);
		Scanner sc = new Scanner(System.in);
		int input;
		boolean flag = true;
		while (flag) {
			System.out.println("请输入操作,1 查看整个队列 2 增加元素 3 元素出队列 4 查看头部");
			input = sc.nextInt();
			switch (input) {
			case 1:
				aq.showQueue();
				break;
			case 2:
				System.out.println("请输入要增加的数字");
				int in = sc.nextInt();
				aq.add(in);
				break;
			case 3:
				try {
					int queue = aq.getQueue();
					System.out.println(queue + "出队列了");
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

				break;
			case 4:
				try {
					int showHead = aq.showHead();
					System.out.println("头部是" + showHead);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

				break;
			default:
				break;
			}
		}
		sc.close();
	}
}

class CircleQueue {
	private int maxSize;// 队列容量
	private int front;// 队列头,起始为0,表示队列第一个有值的元素的位置
	private int rear;// 队列尾,起始为0,表示队列最后一个有值的元素的下一个位置
	private int[] arr;// 存放数据模拟队列

	public int getRear() {
		return rear;
	}

	public void setRear(int rear) {
		this.rear = rear;
	}

	public CircleQueue(int maxSize) {
		this.maxSize = maxSize;// 传入的容量设置为队列容量,但预留最后一个空间为空
		front = 0;// 指向队列头部的位置
		rear = 0;// 指向队列尾部的下一个位置,并且空出最后一个空间
		arr = new int[maxSize];// 设置存放数据的数组的大小
	}

	// 判断队列是否满
	public boolean isFull() {
		return (rear + 1) % maxSize == front;// 可带数字验算得出,比如容量为4,只能装3个元素。当front是0,rear是3时则满了,因为arr[0]和arr[1],arr[2]都装了
												// 再比如,front是1,有3个元素arr[1],arr[2],arr[0],此时rear是0(下标3的下一个就变回0)
	}

	// 判断队列是否为空
	public boolean isEmpty() {
		return front == rear;// 头和尾指向同一个位置证明是空
	}

	// 添加数据到队列
	public void add(int n) {
		// 如果满了则不能添加
		if (isFull()) {
			System.out.println("满了,不能加数据");
			return;
		}
		arr[rear] = n;// 把数据放入最后一个有元素的位置的下一个(即rear)
		rear = (rear + 1) % maxSize;// 后移,但要考虑取模问题
	}

	// 数据出队列
	public int getQueue() {
		// 如果为空,则抛出异常
		if (isEmpty()) {
			throw new RuntimeException("队列为空,没有数据可以出队列");
		}
		int val = arr[front];
		arr[front] = 0;
		front = (front + 1) % maxSize;// 取完数据后,让头部向下一个位置移动,考虑取模的问题
		return val;
	}

	// 显示队列的所有数据
	public void showQueue() {
		// 如果为空
		if (isEmpty()) {
			System.out.println("队列空,没数据显示");
			return;
		}
		// 从front开始,遍历有多少个值
		for(int i = front;i<=front + showValuesCount();i++) {
			System.out.println("arr ["+ i%maxSize + "]的值是 "+arr[i%maxSize]);
		}

	}

	// 求出当前队列有多少个值
	public int showValuesCount() {
		return (rear + maxSize - front) % maxSize;//假如maxsize是4,front是1,rear是3,即当前arr[1]和arr[2]是有值的,值的个数为2
	}

	// 显示头数据,不是取数据
	public int showHead() {
		// 如果为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空,没有头数据");
		}
		return arr[front];
	}
}







全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐