目录
一、队列简介
二、用数组模拟队列
三、环形队列
一、队列简介队列是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。
二、用数组模拟队列
package Queue;
import java.util.Scanner;
public class ArrayQueue {
//用数组模拟队列
private int maxsize;//队列的最大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//模拟队列
//创建队列的构造器
public ArrayQueue(int arrMaxsize){
this.maxsize=arrMaxsize;
arr=new int[arrMaxsize];
front=-1;//指向队列头的前一个位置
rear=-1;//指向队列尾
}
//判断队列是否已满
public boolean isFull(){
return rear==maxsize-1;
}
//判断队列是否为空
public boolean isEmpty(){
return rear==front;
}
//向队列中添加元素
public void add(int n){
if(isFull ()){
System.out.println ("队列已满，无法继续添加元素！" );
return;
}
arr[++rear]=n;
System.out.println ("添加成功！" );
}
//删除队列的元素
public void delete(){
if(isEmpty ()){
throw new RuntimeException ("队列为空，无法添加元素");
}
front++;
System.out.println ("删除成功" );
}
//显示队列的所有数据
public void show(){
if(isEmpty ()){
System.out.println ("队列为空，无数据" );
return;
}
System.out.println ("队列中的元素为：" );
for(int i=front+1;i<=rear;i++){
System.out.printf("%dn",arr[i]);
}
}
//取队头元素
public int getFront(){
if(isEmpty ()){
throw new RuntimeException ("队列为空，无法取出队头元素");
}
return arr[front+1];
}
public void menu(){
System.out.println ("a(add):向队列中添加元素" );
System.out.println ("d(delete):删除队列元素" );
System.out.println ("s(show):展示队列元素" );
System.out.println ("g(getHead):获取队头元素" );
System.out.println ("e(exit):退出程序" );
}
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue (10);
Scanner sc=new Scanner (System.in);
char ch;
boolean loop=true;
while(loop){
arrayQueue.menu();
ch=sc.next ().charAt (0);
switch (ch){
case 'a':
System.out.println ("请输入要添加的元素" );
int n=sc.nextInt ();
arrayQueue.add (n);
break;
case 's' :arrayQueue.show (); break;
case 'd':arrayQueue.delete ();break;
case 'g':
System.out.println ("队头元素为:" +arrayQueue.getFront ());
break;
case 'e' :loop=false; break;
default:
System.out.println ("您的输入有误！" );
}
}
}
}
三、环形队列
数组模拟队列存在问题：目前数组只能使用一次，不能复用
故将数组使用算法进行改进为一个环形队列取模：%
思路如下：
1.front变量含义变为指向队列的第一个元素，初始值为0
2.rear变量含义为指向队列的后一个元素的后一个位置，初始值为0
3.队列满时：（rear+1）%maxsize==front
4.队列空时：rear==front
5.队列中有效数据的个数：（rear-front+maxsize）%maxsize
package Queue;
import java.util.Scanner;
public class CircleArrayQueue {
//用数组模拟队列
private int maxsize;//队列的最大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//模拟队列
//创建队列的构造器
public CircleArrayQueue(int arrMaxsize){
this.maxsize=arrMaxsize;
arr=new int[arrMaxsize];
front=0;//指向队列的第一个位置
rear=0;//指向队列最后一个元素的后一个位置
}
//判断循环队列是否已满
public boolean isFull(){
return (rear+1)%maxsize==front;
}
//判断循环队列是否为空
public boolean isEmpty(){
return rear==front;
}
//向队列中添加元素
public void add(int n){
if(isFull ()){
System.out.println ("队列已满，无法继续添加元素！" );
return;
}
//直接将数组加入
arr[rear]=n;
//将rear后移，这里必须考虑取模
rear=(rear+1)%maxsize;
System.out.println ("添加成功！" );
}
//删除队列的元素
public void delete(){
if(isEmpty ()){
throw new RuntimeException ("队列为空，无法添加元素");
}
front=(front+1)%maxsize;//防止越界
System.out.println ("删除成功" );
}
//显示队列的所有数据
public void show(){
if(isEmpty ()){
System.out.println ("队列为空，无数据" );
return;
}
System.out.println ("队列中的元素为：" );
for(int i=front;i
