言
本篇介绍队列的定义、队列的实现方式（数组实现队列，链表实现队列），如果你需要了解其他数据结构，请点击下面链接查看！！！
了解更多：数据结构与算法目录整理
队列
一、队列的定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
二、队列的实现方式（顺序存储于链式存储）
1）队列的基本操作及其说明
| 方法名 | 返回值 | 参数类型 | 说明 |
|---|---|---|---|
| isFull() | boolean | 无 | 判断队列是否为满 |
| isEmpty() | boolean | 无 | 判断队列是否为空 |
| add(int data) | void | int | 向队列中添加元素 |
| getOne() | int | 无 | 从队列中去除元素 |
| getHead() | int | 无 | 获取头部元素 |
| getQueue() | List | 无 | 获取队列元素 |
| size() | int | 无 | 获取队列中元素的个数 |
2）队列的数组实现
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import javax.management.RuntimeErrorException;
/**
* *队列的数组实现
* @author 蜡笔小新
*
*/
public class Test3 {
public static void main(String []args) {
boolean temp=true;
ArrQueue arrQueue=new ArrQueue(3);
while(temp) {
System.out.println("isFull:队列是否为满");
System.out.println("isEmpty:队列是否为空");
System.out.println("add:添加元素");
System.out.println("getOne:获取元素");
System.out.println("getHead:获取头部元素");
System.out.println("getQueue:获取队列");
System.out.println("size:获取队列中元素的个数");
System.out.println("exit:退出程序");
System.out.println("输入你的操作命令：");
Scanner scanner=new Scanner(System.in);
String str=scanner.nextLine();
switch(str) {
case "isFull":
System.out.println(arrQueue.isFull());
break;
case "isEmpty":
System.out.println(arrQueue.isEmpty());
break;
case "add":
System.out.println("输入要添加的数据：");
int n=scanner.nextInt();
arrQueue.add(n);
break;
case "getOne":
try {
int m = arrQueue.getOne();
System.out.println(m);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "getHead":
try {
int s=arrQueue.getHead();
System.out.println(s);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "getQueue":
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "size":
System.out.println(arrQueue.size());
break;
case "exit":
temp=false;
break;
default:
System.out.println("输入有误");
break;
}
}
System.out.println("程序退出！");
}
}
class ArrQueue{
private int maxSize; //队列的最大容量
private int front; //队列头
private int rear; //队列尾
private int []arr; //模拟队列
public ArrQueue(int maxSize) {
this.maxSize=maxSize;
front=-1; //指向头部的前一个位置
rear=-1; //指向尾部的位置
arr=new int[maxSize]; //初始化数组
}
//判断队列是否为空
public boolean isEmpty() {
return front==rear;
}
//判断队列是否为满
public boolean isFull() {
return rear==maxSize-1;
}
//向队列中添加元素
public void add(int data) {
if(isFull()) {
System.out.println("队列已满");
return ;
}
arr[++rear]=data;
}
//从队列中去除元素
public int getOne() throws Exception{
if(isEmpty()) {
throw new Exception("队列为空");
}
return arr[++front];
}
//size() int 无 获取队列中元素的个数
//getHead() int 无 获取头部元素
public int getHead() throws Exception {
if(isEmpty()) {
throw new Exception("队列为空");
}
return arr[front+1];
}
//获取队列元素
public List getQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
List list=new ArrayList<>();
for(int i=front+1;i<=rear;i++) {
list.add(arr[i]);
}
return list;
}
//获取队列元素个数
public int size() {
if(isEmpty()) {
return 0;
}
return rear+1;
}
} 复制
运行结果：
以上就是队列的数组实现，但是我们发现以上方法只能使用一次，无法做到复用的效果，因此对以上代码进行修改如下：
对以上程序中的 getOne()方法进行修改
//从队列中去除元素
public int getOne() throws Exception{
if(isEmpty()) {
throw new Exception("队列为空");
}
int t=arr[++front];
if(isEmpty()) {
front=rear=-1;
}
else {
for(int i=front+1;i<=rear;i++) {
arr[i-1]=arr[i];
}
front--;
rear--;
}
return t;
} 复制
3）队列的链表实现
正在神速整理中。。。。。敬请期待