概述
队列的设计与实现及应用
一、目的和要求:
(1)正确定义队列(顺序队或链队);
(2)掌握队列基本操作实现方法;
(3)能正确分析算法的时间复杂度;
(3)采用队列解决实际问题。
二、实验原理及内容:
(1)定义队列(顺序队列或链队列);
(2)队列基本操作实现方法;
(3)采用队列解决实际问题(银行排队叫号服务)。
三、实验步骤:(以链队列为例实现,也可以自行采用顺序队列实现)
(1)定义链队列;
(2)链队列基本操作实现方法;
(3)采用链队列解决银行排队叫号服务问题。
四、实验过程
1、工程结构如下图所示:
2、队列接口定义:IStack.java
public interface IQueue<E> {
boolean in(E item);//入队列操作
E out(); //出队列操作
E head(); //取对头元素
int size();//求队列的长度
boolean isEmpty();//判断队列是否为空
boolean isFull();//判断队列是否为满
void clear();//清空队列
}
3、顺序队列的定义及实现:SeqQueue.java
import java.lang.reflect.Array;
public class SeqQueue<E> implements IQueue<E> {
private int maxsize; //队列的容量
private E[]data; // 存储循环顺序队列中的数据元素
private int front; // 指示最近一个己经离开队列的元素所占的位置
private int rear; // 指示最近一个进行入队列的元素的位置
private int size;
public int getMaxsize() {
returnmaxsize;
}
public void setMaxsize(int maxsize) {
this.maxsize = maxsize;
}
public E[] getData() {
returndata;
}
public void setData(E[] data) {
this.data = data;
}
public int getFront() {
returnfront;
}
public void setFront(int front) {
this.front = front;
}
public int getRear() {
returnrear;
}
public void setRear(int rear) {
this.rear = rear;
}
//初始化队列
@SuppressWarnings("unchecked")
public SeqQueue(Class<E> type,int maxsize) {
data = (E[]) Array.newInstance(type,maxsize);
this.maxsize = maxsize;
}
//入队列操作
public boolean in(E item) {
if(isFull())return false;
data[rear] = item;
rear = (rear+1)%maxsize;
size++;
return true;
}
public int getSize() {
returnsize;
}
public void setSize(int size) {
this.size = size;
}
//出队列操作
public E out() {
if(isEmpty())
return null;
E i = data[front];
front = (front + 1)%maxsize;
size--;
return i;
}
//取对头元素
public E head() {
if(isEmpty())
return null;
return
data[front];
}
//求队列的长度
public int size() {
return (rear+maxsize-front)%maxsize;
}
// 判断队列是否为空
public boolean isEmpty() {
if(front ==rear)
return true;
return false;
}
// 判断循环顺序队列是否为满
public boolean isFull() {
if(size ==maxsize)
return true;
return false;
}
//清空队列
public void clear() {
size =0;
front = rear = 0;
}
}
4、顺序队列的测试:TestQueue.java
public class TestQueue {
public static void main(String[] args) {
int[] data={23,45,3,7,6,945};
//注意给定的循环队列长度至少要比实际长度大1
IQueue<Integer> queue=new SeqQueue<Integer>(Integer.class,data.length+1);
//IQueue<Integer> queue=new LinkQueue<Integer>();
//入队操作
System.out.println("*******入队操作*******");
for(int i=0; i<data.length;i++){
queue.in(data[i]);
System.out.println(data[i]+"入队");
}
int size=queue.size();
//出队操作
System.out.println("*******出队操作*******");
for(int i=0; i<size;i++){
System.out.println(queue.out()+"出队 ");
}
}
}
5、链队结点的定义
class QueueNode<E>
{
private Edata; // 数据域
private QueueNode<E> next; // 引用域
//get和set方法
public E getData() {
returndata;
}
public void setData(E data) {
this.data = data;
}
public QueueNode<E> getNext() {
returnnext;
}
public void setNext(QueueNode<E> next) {
this.next = next;
}
//构造函数
public QueueNode(){}
public QueueNode(E data) {
this.data = data;
}
public QueueNode(E data,QueueNode<E> next) {
this.data = data;
this.next = next;
}
}
6、链队的定义及实现
public class LinkQueue<E> implements IQueue<E> {
private QueueNode<E>front; // 队列头指示器
private QueueNode<E>rear; // 队列尾指示器
private int size; // 队列数据元素个数
// 初始化链队列
public LinkQueue() {
front = rear = null;
size = 0;
}
// 入队列操作
public boolean in(E item) {
QueueNode<E> q = new QueueNode<E>(item);
if(front ==null)
{
front = rear = q;
}else{
rear.setNext(q);
rear = q;
}
size++;
return true;
}
// 出队列操作
public E out() {
if(size == 0)
return null;
E i = front.getData();
front = front.getNext();
size--;
return i;
}
// 取对头元素
public E head() {
returnfront.getData();
}
// 求队列的长度
public int size() {
returnsize;
}
// 判断队列是否为空
public boolean isEmpty() {
if(rear ==front)
return true;
return false;
}
//清空队列
public void clear() {
front = rear = null;
size =0;
}
}
7、银行叫号实现(排队机)
public class TestBankQueue {
public static void main(String[] args){
int windowcount =2;//设置银行柜台的服务窗口数。先设为1,然后依次增加看效果
//创建服务窗口数组
ServiceWindow[] sw = new ServiceWindow[windowcount];
//创建排队机对象
QueueMachine qm=new QueueMachine("0800","1630");
//启动排队机服务
qm.start();
for (int i = 0; i < windowcount; i++)
{
//初始化服务窗口数组
sw[i] = new ServiceWindow(qm.getQueue());
//将名字设置为服务窗口的编号
sw[i].setName( "" + (i + 1));
//启动窗口服务
sw[i].start();
}
}
}
8、银行叫号实现(测试主类)
import java.util.Date;
import java.text.SimpleDateFormat;
import java.util.Scanner;
public class QueueMachine extends Thread {
private int number;//排队机当前最新号码
private IQueue<Integer> queue;//排队机维持的队列
private String starttime;//排队机工作开始时间,例如:0800为早上8点
private String endtime;//排队机工作结束进间例如:1630为下午4点半
public QueueMachine( String starttime,String endtime){
queue=new SeqQueue<Integer>(Integer.class,100);
//queue=new LinkQueue<Integer>();
this.starttime=starttime;
this.endtime=endtime;
}
//获取服务队列
public IQueue<Integer> getQueue() {
return queue;
}
//顾客按回车获取服务号,将服务号入队、打印服务小票
public void run(){
Scanner sc=new Scanner(System.in);
SimpleDateFormat df = new SimpleDateFormat("HHmm");//设置日期格式
//获取当前系统时间并转换为设置的日期格式
String time=df.format(new Date());
while (time.compareTo(starttime)>=0 && time.compareTo(endtime)<=0)
{
System.out.println("按回车键获取号码:");
sc.nextLine();
int callnumber=++number;
if (queue.in(callnumber))
{
System.out.println(String.format("您的号码是:%d,你前面有%d位,请等待!", callnumber, queue.size()-1));
time=df.format(new Date());
}
else{
System.out.println("现在业务繁忙,请稍后再试!"); //队列满时出现这种情况
number--;
}
}
sc.close();
System.out.println("己到下班时间,请明天再来");
}
}
9、银行叫号实现(服务窗口)
public class ServiceWindow extends Thread {
private IQueue<Integer>queue;//服务队列
//在构造函数中指定服务的队列
public ServiceWindow(IQueue<Integer>queue) {
this.queue =queue;
}
//窗口叫号及银行柜台人员工作时间10000ms
public void run() {
while (true) {
synchronized (queue) {
if (queue.size()>0) {
System.out.println(String.format("请%d号到%s号窗口!",
queue.out(), Thread.currentThread().getName()));
}
}
try {
Thread.sleep(10000);
} catch (InterruptedException e) {
System.out.println(e.getMessage());
}
}
}
}
转载于:https://www.cnblogs.com/new-zjw/p/8540917.html
最后
以上就是平常缘分为你收集整理的java_实现队列以及实例队列的设计与实现及应用的全部内容,希望文章能够帮你解决java_实现队列以及实例队列的设计与实现及应用所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复