时间戳

首页 > 技术文章 > java_实现队列以及实例

java_实现队列以及实例

new-zjw 2017-10-24 09:36 原文

队列的设计与实现及应用

一、目的和要求：

（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());
           }
       }
    }
}

推荐阅读