1. 首页
  2. 文章中心
  3. java数据结构

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

118 阅读 0 评论
我是靠谱客的博主 谨慎店员，这篇文章主要介绍环形队列--通过数组实现，现在分享给大家，希望可以做个参考。

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

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

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

创建相关变量

复制代码
1
2
3
4
5
private int maxSize;
private int front;  //这里front指向队列的第一个元素
private int rear;   //这里rear指向队列的最后一个元素的后一个位置
private int[] arr;

创建构造器

复制代码
1
2
3
4
5
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相等。

复制代码
1
2
3
4
public boolean isFull() {
	return (rear + 1) % maxSize == front;
}

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

复制代码
1
2
3
4
public boolean isEmpty() {
	return rear ==front;
}

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
public void addQueue(int n) {
	if(isFull()) {
		System.out.println("队列满");
		return;
	}
	//直接将数据加入
	arr[rear] = n;
	//将rear后移，这里必须考虑取模
	rear = (rear + 1) % maxSize;
}

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

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

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

复制代码
1
2
3
4
public int size() {
	return (rear + maxSize - front) % maxSize;
}

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
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]);
	}
}

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

复制代码
1
2
3
4
5
6
7
public int headQueue() {
	if(isEmpty()) {
		throw new RuntimeException("队列空");
	}
	return arr[front];
}

完整代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
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];
	}
}

最后

以上就是谨慎店员最近收集整理的关于环形队列--通过数组实现的全部内容，更多相关环形队列--通过数组实现内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(78)

相关文章

数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表
数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表
循环队列数组模拟环形队列代码实现
循环队列数组模拟环形队列代码实现
错题整理（422）
错题整理（422）
数组中元素与字节的关系
数组中元素与字节的关系
环形队列--通过数组实现
环形队列--通过数组实现
使用数组模拟队列以及优化环形队列详情请看代码注释：环形队列：
使用数组模拟队列以及优化环形队列详情请看代码注释：环形队列：
线性表
线性表
2020-11-14 数据结构与算法（2）顺序表
2020-11-14 数据结构与算法（2）顺序表

评论列表共有 0 条评论

立即
投稿
返回
顶部