Java实现数组模拟队列详解与代码

概念

队列是一种特殊的线性表，严格遵循先进先出（FIFO：first input first output）原则。即最早进入队列的元素最先被移除，最后进入的元素最后被移除。这种机制类似于现实中商场排队结账的场景。

在具体实现上，通常使用两个指针（或索引）来标识队列的状态：front 指向队列头部的前一个位置，rear 指向队列尾部当前的有效数据。通过这两个指针的移动和比较，可以完成入队和出队操作。

队列的基本操作

队列主要包含两种核心操作：

• 插入值操作（入队 / enqueue）：在队列尾部添加新元素，参数为需要插入的数据 data。
• 删除值操作（出队 / dequeue）：从队列头部移除元素，无参，返回被移除的值。

队列状态判定条件

在使用数组模拟时，需要根据 front 和 rear 的值来判断队列的边界情况：

• 队空：当 front == rear 时，表示队列为空。
• 队满：当 rear == maxSize - 1（假设数组最大容量为 maxSize）时，表示队列已满，无法继续添加元素。
• 非空：若 front != rear，则队列中至少有一个元素。
• 计算长度：队列中当前元素的总数可以使用公式 (REAR - FRONT) 计算得出。

数组实现队列

队列的实现方式多样，包括堆栈和链表等，其中利用定长数组是最基础的实现方法。我们将创建一个名为 ArrayQueue 的类，内部维护一个整型数组及最大容量，并通过构造器初始化指针。

第1步：编写 ArrayQueue 核心类

该类定义了队列的属性及关键业务逻辑，具体代码如下：

class ArrayQueue {
	private int maxSize; // 数组的最大容量
	private int front; // 队列头指针，指向队列头的前一个位置
	private int rear; // 队列尾指针，指向队列尾的数据(最后一个数据)
	private int[] arr; // 存放数据的数组，用于模拟队列
 
	// 创建构造器，进行初始化
	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1; // front 初始化为 -1
		rear = -1;  // rear 初始化为 -1
	}
 
	// 判断队列是否已满
	public boolean isFull() {
		return rear == maxSize - 1;
	}
 
	// 判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}
 
	// 向队列中添加数据
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("队列已满，不能再添加数据了！");
			return;
		}
		rear++; // 让 rear 指针后移
		arr[rear] = n; // 将新数据放入末尾
	}
 
	// 从队列取出数据（出队）
	public int getQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空，无数据可取！");
		}
		front++; // front 指针后移
		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("队列为空，没有数据~~");
		}
		return arr[front + 1];
	}
}

第2步：编写主函数进行测试交互

在主程序中，我们实例化一个大小为 3 的队列，并使用 Scanner 接收用户输入的命令，展示各项操作的效果：

// 创建一个容量为 3 的队列对象
ArrayQueue queue = new ArrayQueue(3);
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': // 显示队列所有数据
		queue.showQueue();
		break;
	case 'a': // 添加数据
		System.out.println("请输入要添加的数字:");
		int value = scanner.nextInt();
		queue.addQueue(value);
		break;
	case 'g': // 依次取出数据
		try {
			int res = queue.getQueue();
			System.out.printf("取出的数据是%d\n", res);
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
		break;
	case 'h': // 查看队列头指向
		try {
			int res = queue.headQueue();
			System.out.printf("队列头的数据是%d\n", res);
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
		break;
	case 'e': // 退出程序
		scanner.close();
		loop = false;
		break;
	default:
		break;
	}
}

System.out.println("程序退出~~");

以上就是Java中如何用数组实现基本队列的详细内容，更多关于Java集合框架与常用算法的资料请关注本站其它相关文章！