Python 官方文档:入门教程 => 点击学习
1.队列的基本概念 什么是队列? 队列是一种特殊的线性表它只允许在表的前端(队头)进行删除操作在表的后端(队尾)进行插入操作队列是一个有序表(可以用数组或链表实现)队列先进先出队列开
什么是队列?
顺序队列中的溢出现象:
在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。自己真从MaxSize-1
增1变到0,可用取余运算rear%MaxSize
和front%MaxSize
来实现。这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列
由于普通队列存在溢出问题所以这里用数组来实现环形队列
:(rear+1) % maxSize = front
rear = front
:(rear+maxSize-front) % maxSize
为什么队列满的条件是(rear+1) % maxSize = front
(1)假设rear>front
rear-front=maxSize-1
rear+1-maxSize=front
由于当rear>front
队列满时rear+1
一定等于maxSize
(rear+1) % maxSize = rear+1-maxSize =0
(2)假设front>rear
front-rear=1
rear+1=front
由于当front>rear
时rear+1
一定小于maxSize
所以(rear+1) % maxSize=rear+1
(3)有上述所示可以得出队列满的条件是(rear+1) % maxSize = front
元素个数的计数与这相似
public class Queue {
private int maxSzie; //队列中能存储的最大个数
private int frontPoint; //头指针指向队头
private int rearPoint; //尾指针指向队尾的后一个数据
private int[] array; //模拟队列的数组
public Queue(int max) {
maxSzie = max;
frontPoint = 0;
rearPoint = 0;
array = new int[max];
}
public boolean isEmpty(){
return frontPoint == rearPoint;
}
public boolean isFull(){
return (rearPoint+1)%maxSzie == frontPoint;
}
public void add(int x){
if (isFull()){
System.out.println("当前队列已满");
return;
}
//添加数据
array[rearPoint] = x ;
//后移尾指针
rearPoint = (rearPoint+1) % maxSzie;
System.out.println("添加成功");
}
public int remove(){
if (isEmpty()){
throw new RuntimeException("当前队列为空");
}
//把队头的值赋值给临时变量
int x = array[frontPoint];
//移除数据后头指针需要向后移动 时其指向新的队头
frontPoint = (frontPoint+1) % maxSzie;
System.out.println("移除成功");
return x;
}
public int gethead(){
if (isEmpty()){
throw new RuntimeException("当前队列为空");
}
return array[frontPoint];
}
public void show(){
int x = 0;
for (int i = frontPoint; i <= (rearPoint+maxSzie-frontPoint)%maxSzie; i++) {
x++;
System.out.println("队列的第"+x+"个数据是"+array[i]);
}
}
}
public class QueueTest {
public static void main(String[] args) {
Queue queue = new Queue(5);
Scanner scanner = new Scanner(System.in);
char systemIn = ' ';
boolean noEnd = true;
while (noEnd){
System.out.println("a:add(添加数据)");
System.out.println("r:remove(删除数据)");
System.out.println("h:head(获取队头)");
System.out.println("s:show(遍历队列)");
System.out.println("e:exit(退出程序)");
System.out.println("请输入字符");
systemIn = scanner.next().charAt(0);
switch (systemIn){
case 'a':
System.out.println("请输入入队的数据(数字)");
int x = Integer.parseInt(scanner.next());
queue.add(x);
break;
case 'r':
queue.remove();
break;
case 'h':
int head = queue.gethead();
System.out.println("队头是"+head);
break;
case 's':
queue.show();
break;
case 'e':
noEnd = false;
break;
}
}
}
}
到此这篇关于Java队列数据结构的实现的文章就介绍到这了,更多相关Java队列数据结构内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java队列数据结构的实现
本文链接: https://www.lsjlt.com/news/159971.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0