目录
题目描述
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
顺序队列：建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。在入队、出队过程中，可能需要频繁移动数据。
循环队列：在实际使用队列时，为了使队列空间能重复使用，减少数据移动次数，对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置（可以使用取余运算rear%MaxSize和front%MaxSize实现，MaxSize表示数组容量）。这实际上把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列称为循环队列。
使用面向对象的思想实现循环队列，队列中的元素存放在数组中。其主要功能为：
（1）数据元素入队 （2）数据元素出队 （3）队列是否为空
（4）队列是否为满 （5）查询数据元素是否在队列中 （6）返回队列中元素个数
某学校安排学生与教师做健康体检活动，学生的属性包括学号、姓名等，方法包括带参构造方法，返回学生信息字符串的方法（返回学号与姓名，之间用英文逗号分隔）。教师的属性包括职工号、姓名、家庭住址等，方法包括带参构造方法，返回教师信息字符串的方法（返回职工号、姓名与家庭住址，之间用英文逗号分隔）。这两个类在设计时要求用继承的思想进行设计。
在主类中，定义队列对象存储排队中的学生与教师信息。输入一个整数表示队列能容纳的最大人数。按输入选项完成相应操作：0-结束程序，1-排队等待体检，2-体检完成出队，3-按照姓名查找某个人，4-输出队列中人员数。选项为1时（排队），输入a表示学生，b表示教师，并输入相应的完整信息，若队列未满，则该人入队，否则输出“queue is full,operation failed”；选项为2时，若队列未空，则应输出出队的人员信息，否则输出“queue is empty,operation failed”；选项为3时，输入姓名，输出队列中相应的人员信息，一个人员信息独立成行，若查询不到信息则输出“no found”。
输入
队列最大容量，选项及其对应的输入信息
输出
相应信息
样例输入 Copy
3 1 a x001 aa 1 b j001 aa 15-1-101 1 a x002 bb 4 3 aa 1 b j002 cc 12-2-201 3 cc 2 0
样例输出 Copy
3 x001,aa j001,aa,15-1-101 queue is full,operation failed no found x001,aa
提示
提示：在使用Java语言编写实现循环队列时，一般可以使用两种方式判断队列是否已满（任选其一）：
（1）增加一个属性size用来记录目前的元素个数。当front=rear时，size=0表示队列为空，size=数组长度表示队列已满。
（2）数组中只存储“数组大小-1”个元素，保证rear转一圈之后不会和front相等，也就是队列满的时候，rear+1=front，中间刚好空一个元素。
代码实现
package shiyan33;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt(); //列表容量
Queue queue = new Queue(max); //初始一个循环列表
while(true) {
int mark = sc.nextInt(); //选择标记
switch(mark) {
case 1:
String option = sc.next(); //输入对象类型a为学生b为老师
Object obj = null; //定义一个对象用来接受学生或者老师对象
if(option.equals("a")) {
String studentId = sc.next();
String name = sc.next();
obj = new Student(studentId, name); //定义一个学生对象
}else if(option.equals("b")) {
String Id = sc.next();
String name = sc.next();
String address = sc.next();
obj = new Teacher(Id, name, address);//定义一个老师对象
}else {
System.out.println("输入错误");
}
if(!queue.enqueue(obj)) { //进行添加，添加失败进行下面操作
System.out.println("queue is full,operation failed");
}
break;
case 2:
Object obj2 = queue.dequeue(); //进行删除操作，返回一个Object对象
if(obj2!=null) { //如果对象不为空则打印对象信息
System.out.println(obj2);
}else {
System.out.println("queue is empty,operation failed");//删除失败说明列表为空
}
break;
case 3:
String s = sc.next();
queue.traverse(s); //遍历查找操作
break;
case 4:
System.out.println(queue.getSize()); //打印列表大小
}
if(mark == 0) {
break;
}
}
}
}
class Student{
private String studentId;
private String name;
public Student(String studentId, String name) {
super();
this.studentId = studentId;
this.name = name;
} //以上是属性和构造方法的定义
public String getName() {
return name;
} //获得名字方便查找操作，其他的属性不需要所以就不设置get方法了
@Override //toSring改写，方便打印
public String toString() {
// TODO Auto-generated method stub
return studentId + "," + name;
}
}
class Teacher{ //和学生类相似就不多介绍
private String teacherId;
private String name;
private String address;
public Teacher(String teacherId, String name, String address) {
super();
this.teacherId = teacherId;
this.name = name;
this.address = address;
}
public String getName() {
return name;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return teacherId + "," + name + "," + address;
}
}
class Queue{
private Object[] obj; //循环列表定义
private int front = 0; //列表头指针
private int rear = 0; //尾指针
private int size = 0; //列表大小
private int max; //列表容量
public Queue(int max) {
super();
this.max = max;
obj = new Object[max]; //有参构造，将max初始化
}
public boolean isEmpty() { //判断列表是否为空
return size == 0;
}
public boolean isFull() { //判断列表是否为满
return size == max;
}
public int getSize() { //获取列表大小
return size;
}
public boolean enqueue(Object o) { //添加列表元素
if(!isFull()) { //判断是否满
obj[rear] = o; //列表未满，在尾指针处添加对象
size++; //列表大小加一
rear++;
rear %= max; //尾指针往后移动一个单位，但注意这是个循环的，所以进行取余
return true;
}
return false; //插入失败返回false
}
public Object dequeue() {
if(!isEmpty()) { //列表非空进行下面操作
Object o = obj[front]; //先把要删除的对象存起来，等会返回
size--; //列表大小-1
front++; //头指针往后移动1个单位，并进行取余操作
front %= max;
return o; //返回删除的对象
}
return null; //否则返回空对象
}
public void traverse(String s) {
boolean mark = true; //标记是否找到符合要求的对象
if(size==0) { //列表为空直接打印 并结束
System.out.println("no found");
return;
}
for (int i = front; i-front < size; i++) { //遍历列表寻找符合要求的对象
if(obj[i%max] instanceof Student) { //如果是学生对象
Student o = (Student) obj[i%max]; //进行强制转换
if(o.getName().equals(s)) { //判断名字是否相同
System.out.println(o.toString());
mark = false; //寻找到了重新标记
}
}else if(obj[i%max] instanceof Teacher) { //与上面类似
Teacher o = (Teacher) obj[i%max];
if(o.getName().equals(s)) {
System.out.println(o.toString());
mark = false;
}
}
}
if(mark) {
System.out.println("no found");
}
}
}