首页 / 算法 / 数据结构和算法02--队列
数据结构和算法02--队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构和算法02--队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5365字,纯文字阅读大概需要8分钟。
内容图文
![数据结构和算法02--队列](/upload/InfoBanner/zyjiaocheng/593/29fb32884ec94433960e5964555ab862.jpg)
? 队列:先进先出、用链表或数组实现。
一、一般的队列
1、思路:
? 模拟简单队列——队首走的位置不能再添加。
? 实现方式:两个指针,一个指向队首front、一个指向队尾rear。指向队首的负责取出数据,指向队尾的负责添加数据。
? 难点:在于添加和取出数据时,指针应先操作该位置数据然后再移动指针,不然指针就没了。
2、代码
? 代码实现思路:先创建数组队列-->添加判断为空、已满、放入数据、取出数据、遍历队列、查看头节点的方法-->main方法写测试代码。
//测试最基本的队列
public class BasicQueue01 {
//9、创建主方法用于测试
public static void main(String[] args) {
//创建一个队列
ArrayQueue arrQueue = new ArrayQueue(4);
//用于接收用户输入信息
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':
arrQueue.showQueue();
break;
case 'a':
System.out.println("请输入一个数");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g':
try {
int num = arrQueue.getQueue();
System.out.println(num);
}catch(RuntimeException e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int headQueue = arrQueue.headQueue();
System.out.println("第一个数据是" + headQueue);
}catch(RuntimeException e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
default:
break;
}
}
System.out.println("程序退出啦");
}
}
class ArrayQueue{
//1、先给出队列的各种属性
private int maxSize;
private int front;
private int rear;
private int[] arr;
//2、给一个队列的构造方法
public ArrayQueue(int arrmaxSize) {
maxSize = arrmaxSize;
front = -1;
rear = -1;
arr = new int[maxSize];
}
//3、判断队列是否已满
public boolean isFull() {
return rear == maxSize - 1;
}
//4、判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
//5、添加数据到队列
public void addQueue(int n) {
//(1)先判断队列是否已满
if(isFull()) {
System.out.println("队列已满,不能添加~~");
return;
}
//(2)如果不满的话,那就在后面加一格,然后加数据
rear++;
arr[rear] = n;
}
//6、获取队列的数据,出队列
public int getQueue() {
//(1)先判断队列是否为空
if(isEmpty()) {
throw new RuntimeException("队列为空,不能获取~~");
}
//(2)如果不为空的话,那就把指向第一个的前面这个指针,指向第一个,然后取出来,以此类推
front++;
return arr[front];
}
//7、查询队列
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+1,arr[i]);
}
System.out.println();
}
//8、显示队列的头数据
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,无法显示");
}
return arr[front+1];
}
}
二、循环队列
1、思路
? 解决普通队列不能不能在前面位置再添加的问题。
? 改成环形队列这样就可以反复添加了。
? 但是这里要注意到最大值后就返回到初始值了。
? 实现方式:front、rear指针,每添加一个rear指向当前位置后一个,浪费一个元素,指到最后一个元素为满。
? 难点:因为满了又跳到0,所以得注意front/rear + 1可能回到初始位置,并且得注意rear - front可能存在小减大的情况,所以判断有几个元素的时候不能直接用rear - front的方式。
2、代码
? 代码实现思路:先创建数组队列-->添加判断为空、已满、放入数据、取出数据、遍历队列、查看头节点的方法-->main方法写测试代码。
//测试环形队列
public class CircleArrayQueue01 {
public static void main(String[] args) {
System.out.println("测试数组模拟环形队列的案例~~~");
CircleQueue circleQueue = new CircleQueue(4);
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':
circleQueue.showQueue();
break;
case 'a':
System.out.println("请输入一个数");
int num = scanner.nextInt();
circleQueue.addQueue(num);
break;
case 'g':
try {
int result = circleQueue.getQueue();
System.out.printf("查到的数据是%d\n",result);
}catch(RuntimeException e) {
System.out.println(e.getMessage());
}
break;
case 'h':
int result = circleQueue.headQueue();
System.out.printf("查到的数据是%d\n",result);
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("退出程序~~");
}
}
class CircleQueue{
//属性
private int maxSize;
private int front;
private int rear;
private int[] arr;
//构造函数
public CircleQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
//判断是否为空
public boolean isEmpty() {
return rear == front;
}
//判断是否已满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
//添加数列到队列
public void addQueue(int num) {
if(isFull()) {
System.out.println("队列已满,无法加入");
return;
}
arr[rear] = num;
rear = (rear + 1) % maxSize;
}
//获取队列数据,出队列
public int getQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,不能取数据");
}
int value = arr[front];
front = (front + 1)% maxSize;
return value;
}
//显示队列所有数据
public void showQueue() {
if(isEmpty()) {
System.out.println("队列为空,不能显示");
return;
}
for(int i = front;i < front + size() ;i++) {
System.out.printf("arr[%d] = %d\n",i%maxSize,arr[i%maxSize]);
}
}
//求出当前队列的有效数据
public int size() {
return (rear + maxSize - front) % maxSize;
}
//显示队列的头数据
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,没有数据");
}
return arr[front];
}
}
内容总结
以上是互联网集市为您收集整理的数据结构和算法02--队列全部内容,希望文章能够帮你解决数据结构和算法02--队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。