环形队列--通过数组实现

在上一篇的数组队列中，数组只能使用一次就不能用给了，一旦把输入的数据全部都取出，再添加数据时就会出错，不能达到复用的效果。为了能重复的使用同一个数组，就要使用环形队列（通过取模方式）。

以下为java代码实现的环形队列

首先创建一个类CircleArray来创建实例域和初始化队列，并实现相关的功能。

创建相关变量

private int maxSize;
private int front;  //这里front指向队列的第一个元素
private int rear;   //这里rear指向队列的最后一个元素的后一个位置
private int[] arr;

创建构造器

public CircleArray(int arrMaxSize) {
	maxSize = arrMaxSize;
	arr = new int[maxSize];
}

创建方法，判断队列是否满，rear的值为数组中的位置，若队列时满的，则rear+1取模后的值就会与front相等,假如rear为1，front为2，maxSize为3，则（1+1）% 3 = 2，与front相等。

public boolean isFull() {
	return (rear + 1) % maxSize == front;
}

创建方法，判断队列是否为空，数据取出时队头front会向后移，当数据全部取出时，front == rear。

public boolean isEmpty() {
	return rear ==front;
}

创建方法，添加数据到队列， 先判断队列是否满，若满了就不能加数据，若不满，就把要加入的数据n加入到队尾arr[rear]，加入之后，rear需要后移（通过取模方式）

public void addQueue(int n) {
	if(isFull()) {
		System.out.println("队列满");
		return;
	}
	//直接将数据加入
	arr[rear] = n;
	//将rear后移，这里必须考虑取模
	rear = (rear + 1) % maxSize;
}

创建方法，获取队列的数据，出队列

public int getQueue() {
	if(isEmpty()) {
		//通过抛出异常
		throw new RuntimeException("队列空");
	}
	//这里需要分析出front是指向队列的第一个元素
	//1.先把front对应的值保留到一个临时变量
	//2.将front后移，考虑取模
	//3.将临时保存的变量返回
	int value = arr[front];
	front = (front+1) % maxSize;
	return value;
}

创建方法，显示队列的所有数据前，要先求出当前队列有效数据的个数

public int size() {
	return (rear + maxSize - front) % maxSize;
}

创建方法，显示队列的所有数据，先判断是否空，若不空，则用for循环开始遍历，遍历的开始为front在数组中的位置，遍历的次数为size()次，这样遍历让数组从front开始遍历，并让arr[]这里面的参数能通过取模实现读取数组前面序列的数据，实现遍历环形队列。

public void showQueue() {
	//遍历
	if(isEmpty()) {
		System.out.println("队列空");
		return;
	}
	//从front开始遍历 ,i有可能超过数组的大小，所以要取模
	for (int i = front; i < front + size(); i++) {
		System.out.printf("arr[%d]=%dn", i % maxSize,arr[i % maxSize]);
	}
}

创建方法，显示队列的头数据，注意不是取出数据

public int headQueue() {
	if(isEmpty()) {
		throw new RuntimeException("队列空");
	}
	return arr[front];
}

完整代码

package algorithm.queue;

import java.util.Scanner;

//实现环形队列

public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		//测试
		System.out.println("测试数据模拟环形队列");
		
		//测试
		CircleArray queue = new CircleArray(4);  //队列有效数据最大为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("取出的数据是%dn", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h': // 查看队列头的数据
				try {
					int res = queue.headQueue();
					System.out.printf("队列头的数据是%dn", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e': // 退出
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("程序退出");

	}
}


class CircleArray{
	private int maxSize;
	private int front;  //这里front指向队列的第一个元素
	private int rear;   //这里rear指向队列的最后一个元素的后一个位置
	private int[] arr;
	
	//构造器
	public CircleArray(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}
	
	//判断队列是否满
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}
	
	//判断队列是否为空
	public boolean isEmpty() {
		return rear ==front;
	}
	
	//添加数据到队列
	public void addQueue(int n) {
		if(isFull()) {
			System.out.println("队列满");
			return;
		}
		//直接将数据加入
		arr[rear] = n;
		//将rear后移，这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}
	
	//获取队列的数据，出队列
	public int getQueue() {
		if(isEmpty()) {
			//通过抛出异常
			throw new RuntimeException("队列空");
		}
		//这里需要分析出front是指向队列的第一个元素
		//1.先把front对应的值保留到一个临时变量
		//2.将front后移，考虑取模
		//3.将临时保存的变量返回
		int value = arr[front];
		front = (front+1) % maxSize;
		return value;
	}
	
	//显示队列的所有数据
	public void showQueue() {
		//遍历
		if(isEmpty()) {
			System.out.println("队列空");
			return;
		}
		//从front开始遍历 ,i有可能超过数组的大小，所以要取模
		for (int i = front; i < front + size(); i++) {
			System.out.printf("arr[%d]=%dn", i % maxSize,arr[i % maxSize]);
		}
	}
	
	//求出当前队列有效数据的个数
	public int size() {
		return (rear + maxSize - front) % maxSize;
	}
	
	//显示队列的头数据，注意不是取出数据
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		return arr[front];
	}
}

最后

以上就是谨慎店员为你收集整理的环形队列--通过数组实现的全部内容，希望文章能够帮你解决环形队列--通过数组实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。