一、队列的使用场景
二、普通队列介绍
三、数组实现队列
四、存在的问题
五、循环队列
一、队列的使用场景
队列在日常生活中十分常见。银行叫号系统、排队等都是队列的应用。
排队的原则是先来后到，即先来的人可以优先办理业务，先离开；排在后面的人需要等待。
二、普通队列介绍
队列是一个有序列表，可以用数组或链表来实现。遵循先入先出的原则。即：先进入队列中的数据先取出。后进入队列的数据后取出。
三、数组实现队列
front 是队列最前元素之前的一个位置。rear 是队列最后一个元素的位置。maxSize 是队列的最大容量。进队时，从队尾进，front 不变，rear++, arr[rear]= 进队列的元素。出队时，从队头出，rear 不变，front++, arr[front]= 出队元素。判断队列为满的条件：rear == maxSize-1判断队列为空的条件：rear == front
代码如下（示例）：
package day_02;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Arrayqueue a = new Arrayqueue(4);
Scanner scanner = new Scanner(System.in);
boolean flag = true;
while(flag) {
System.out.println("s：show");
System.out.println("a:addQueue");
System.out.println("g:getQueue");
System.out.println("h:headQueue");
char str = scanner.next().charAt(0);//获取从键盘输入的第一个字符
switch(str) {
case 's':
a.showQueue();
break;
case 'a':
System.out.println("请输入需要增加的字符");
char str2 = scanner.next().charAt(0);
a.addQueue(str2);
break;
case 'g':
try {
int m = a.getQueue();
System.out.println("取出的数据是："+m);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
break;
case 'h':
try {
int i = a.headQueue();
System.out.println(i);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
break;
}
}
}
}
class Arrayqueue{
private int front;//队列头，表示的是队列最前元素的前一个元素位置。
private int rear;//队列尾，表示队列最后一个元素的位置
private int maxSize;//队列的最大容量
private int[] arrqueue;//声明队列数组
public Arrayqueue(int max){//构造方法，初始化
maxSize = max;
arrqueue = new int[maxSize];
front = -1;
rear = -1;
}
public boolean isFull() {//判断队列是否为满
return rear == maxSize-1;
}
public boolean isEmpty() {//判断队列是否为空
return rear == front;
}
public void addQueue(int queue) {//向队列中添加元素
if(isFull()) {
System.out.println("队列已满，无法向其中添加元素");
return;
}
rear++;
arrqueue[rear] = queue;
}
public int getQueue() throws Exception {//从队列中取得元素
if(isEmpty()) {
throw new Exception("队列为空，无法取得元素");
// return -1;
//此处不能为return ，因为此处是要得到值，如果返回-1，则得到的值即为-1
}
front++;
return arrqueue[front];
}
public void showQueue() {//显示队列
for(int i = 0;i
四、存在的问题
当前数组不能实现复用。需要进行优化
五、循环队列
此处循环队列的详解建议去看《大话数据结构》，讲的非常明白，真心强烈推荐！！！front 为队列头，指向队头所在位置。rear 指向队尾元素的后一个位置。front 和 rear 都初始化为0队列为空的条件是 rear == front队列为满的条件是 （rear+1）%maxSize == front队列的长度为( rear - front +maxSize) % maxSize
代码实现
package day_03;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
QElmType a = new QElmType(4);
Scanner scanner = new Scanner(System.in);
boolean flag = true;
while(flag) {
System.out.println("s：show");
System.out.println("a:addQueue");
System.out.println("g:getQueue");
System.out.println("h:headQueue");
char str = scanner.next().charAt(0);//获取从键盘输入的第一个字符
switch(str) {
case 's':
a.show();
break;
case 'a':
System.out.println("请输入需要增加的字符");
int s = scanner.nextInt();
a.addQueue(s);
break;
case 'g':
try {
int m = a.getQueue();
System.out.println("取出的数据是："+m);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
break;
case 'h':
try {
int i = a.head();
System.out.println(i);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
break;
}
}
}
}
class QElmType{
private int front;
private int rear;
private int maxSize;
private int[] queue;
public QElmType(int size){
maxSize = size;
front = 0;
rear = 0;
queue = 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;
}
queue[rear] = n;
rear = (rear+1)%maxSize;//rear向后移动一位，如果移动出了数组，则回到队列头
}
public int getQueue() throws Exception {//从队列中获取元素
if(isEmpty()) {
throw new Exception("队列为空，无法获取元素");
}
int num = queue[front];
front = (front+1)%maxSize;
return num;
}
public int getSize() {//获取队列的长度
return (rear - front + maxSize)%maxSize;
}
public void show() {
if(isEmpty()) {
System.out.println("没有数据");
return;
}
for(int i = front;i
