1.1应用场景
银行排队:
1.2基本介绍
特点:
- 队列是一个有序列表,可以用数组或是链表来实现。
- 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出
示意图:
解释:MaxSize-1:数组中下标从范围0~MaxSize-1
front:指向队列中的首元素的前一个位置
rear:指向队列中的尾元素
最开始的时候没有存入元素就让front与rear都指向-1 表示不存储任何元素,因为数组的下标从0开始。当添加一个元素的时候(所谓的入队)就让rear先加1后存储,当删除一个元素的时候(所谓的出队)就让front移动一个位置(front始终指向头元素的前一个位置)
代码如下:
package com.atguigu.queue;
import java.util.Scanner;
public class aaa {
public static void main(String[] args) {
ArrayQueue1 queue = new ArrayQueue1(3);
int key=0;
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while(flag) {
System.out.println("1.显示队列 , 2.退出程序 , 3.添加数据到队列(入队) ,4.从队列中取出数据(出队), 5.取对头元素");
key = scanner.nextInt();
switch (key) {
case 1:
queue.showQueue();
break;
case 2:
scanner.close();
flag=false;
break;
case 3:
System.out.println("请输入一个数据,进行入队操作");
int val = scanner.nextInt();
queue.addQueue(val);
break;
case 4:
try {
int data = queue.getQueue();
System.out.println("出队的数据是:"+data);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 5:
try {
int data1 = queue.headQueue();
System.out.println("头数据是:"+data1);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
}
}
}
}
class ArrayQueue1{
private int maxSize;
private int front;
private int rear;
private int[] arr;
int count=0;
public ArrayQueue1(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
public boolean isFull() {
return rear == maxSize-1;
}
public boolean isEmpty() {
return front == rear ;
}
public void addQueue(int data) {
if(isFull()) {
throw new RuntimeException("队列已经满,不能添加数据");
}
rear++;
arr[rear] = data;
}
public int getQueue() {
if(isEmpty()) {
throw new RuntimeException("队列中无数据");
}
front++;
return arr[front];
}
public void showQueue() {
if(isEmpty()) {
System.out.println("队列为空,无法显示数据");
return;
}
for (int i=front+1; i <= rear; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,无法取出头部数据");
}
return arr[++front];
}
}
问题分析并优化
1) 目前数组使用一次就不能用, 没有达到复用的效果
2) 将这个数组使用算法,改进成一个环形的队列 取模:%
1.3环形队列
对前面的数组模拟队列的优化,充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明:
- 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize ==front
- rear == front [空]
- 分析示意图:
可根据这个图进行模拟正常的数组不会有环形的 只是这样画图模拟更直观
package com.atguigu.queue;
import java.util.Scanner;
public class ArrCircleQueue {
public static void main(String[] args) {
CircleQueue queue = new CircleQueue(3);
int key=0;
Scanner scanner = new Scanner(System.in);
boolean flag=true;
while(flag) {
System.out.println("1.显示队列 , 2.退出程序 , 3.添加数据到队列(入队) ,4.从队列中取出数据(出队), 5.取对头元素");
key = scanner.nextInt();
switch (key) {
case 1:
queue.showQueue();
break;
case 2:
scanner.close();
flag=false;
break;
case 3:
System.out.println("请输入一个数据,进行入队操作");
int val = scanner.nextInt();
queue.addQueue(val);
break;
case 4:
try {
int data = queue.getQueue();
System.out.println("出队的数据是:"+data);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 5:
try {
int data1 = queue.headQueue();
System.out.println("头数据是:"+data1);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
}
}
}
}
class CircleQueue{
private int maxSize;
private int front;
private int rear;
private int[] arr;
public CircleQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
public boolean isFull() {
return (rear+1)%maxSize==front;
}
public boolean isEmpty() {
return front == rear ;
}
public void addQueue(int data) {
if(isFull()) {
System.out.println("队列已经满,不能添加数据");
return ;
}
arr[rear] = data;
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.print(arr[i%maxSize]+" ");
}
System.out.println();
}
public int size() {
return (rear + maxSize - front) % maxSize;
}
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空,无取出头部数据");
}
return arr[front];
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)