大家好,欢迎来到IT知识分享网。
队列,就是排队,先到的站前面,先离开,后到的排后面,后离开。对应到计算机中,就是添加元素在队尾,删除元素是在队头,先进先出或后进后出。添加元素也叫入队(enqueue),删除元素也叫出队(dequeue)。当然还可以查看队头元素,队中元素个数,以及是否为空,所以队列提供了API 就是enqueue, dequeue,getFront, size, isEmpty。
使用单链表实现队列
队列在尾部添加元素,在头部删除元素。那就让链表头作为队列的头部,因为链表头部容易执行删除操作(出队)。链表尾部只能作为队列的尾部,执行插入操作(入队)。但链表尾部执行插入操作,有一个问题,那就是每次都要遍历整个链表,找到最后一个元素,才能执行插入操作。为了减少遍历,要再维护一个尾指针,指向链表的尾部。因此,使用单链表实现一个队列,链表需要维护两个指针,头指针和尾指针。头指针指向链表的头部,用于出队。尾指针指向链表尾部,用于入队。
public class LinkedQueue<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
}
}
private Node firstNode; //头指针,队头
private Node lastNode; // 尾指针,队尾
private int size;
public void enqueue(T data){}
public T dequeue(){}
public int size(){}
public boolean isEmpty(){}
public T getFront(){}
public void clear(){}
}
enqueue的实现,就是向链表尾部插入一个节点。创建一个新节点,如果队列(链表)为空,直接让头尾指针都指向它
如果链表不空,让尾节点的next指向它,同时更新尾指针的指向,让它指向最新的尾节点
public void enqueue(T data){ Node newNode = new Node(data); if(isEmpty()){ firstNode = lastNode =newNode; } else { lastNode.next = newNode; lastNode = newNode; }
size++; }
dequeue的实现,就是链表头部删除一个节点。链表为空,肯定是不能被删除的,如果链表不空,取出第一个节点,然后让头指针指向它的next节点就好了,
要注意的是一直删除,头指针会指向null,也就是链表中没有元素了,尾指针也要指向null
public T dequeue(){ if(isEmpty()){ throw new RuntimeException("链表为空"); } T frontData = firstNode.data; firstNode = firstNode.next; if(firstNode == null){ lastNode = null; } size--; return frontData; }
其它几个实现比较简单
public int size(){ return size; } public boolean isEmpty(){ return firstNode == null; } public T getFront(){ if(isEmpty()){ throw new RuntimeException("链表为空"); } return firstNode.data; } public void clear(){ firstNode = null; lastNode = null; }
使用队列模拟现实的队列,比如买奶茶,以测算奶茶店的服务能力。如果要统计1小时内的服务能力,可以计算,在一小时内的到达人数,服务人数,等待时间等等。怎么统计呢?1小时,可以分60分钟,每一分钟检测一次,有没有顾客来,如果有就加到队列中,如果没有,就看有没有顾客在服务,如要有,就继续服务,如果没有,服务下一位顾客。怎么知道有没有人来?由于每一个顾客的到达时间是随机的,可以使用一个随机数,如果生成的随机数小于一个阈值,就说明有顾客到,反之,则没有顾客到。 由于每个顾客的服务时间也不一样,可以再使用一个随机数,计算出服务时间。可以看出有两个类,WaitLine和Customer,在WaitLine中有到达人数(numberOfArrived),服务人数(numberServed), 等待时间(totalTimeWaited),在Customer中有到达时间(arriveTime),服务时间(transactionTime)和排队号码(customerNum)。
public class WaitLine { private int numberOfArrivals; private int numberServed; private int totalTimeWaited; private class Customer { int arriveTime; int transactionTime; int customerNum; Customer(int arriveTime, int transactionTime, int customerNum) { this.arriveTime = arriveTime; this.transactionTime = transactionTime; this.customerNum = customerNum; } } }
现在模拟一下队列的情形,顾客到来的时间是随机的,假设有50%的概率会来,那就表示,只要生成的随机数小于50%,就表明顾客到了,加入队列。顾客的服务时间也是不固定的,可以声明一个最大服务时间,然后和随机数相乘,假设最大服务时间是5s。顾客有没有在服务,就是看它的服务时间有没有到0,如果到了,就表示服务完成,到下一位顾客。
// duration: 要统计的服务时间区间,比如60分钟 // arrivalProbability:每秒钟顾管到达的概率, 比如50% // maxTransactionTime:每位顾客的最长服务时间 public void simulate(int duration, double arrivalProbability, int maxTransactionTime) { var line = new LinkedQueue<Customer>(); // 创建一个队列, var transactionTimeLeft = 0; // 每个顾客服务时间的剩余时间,表示一个顾客在不在服务
// clock就是每一秒,用户的到达时间和用户的服务时间都用clock记录 for (int clock = 0; clock < duration; clock++) { // 监测用户到没到,随机数小于规定的概率,表示有顾客到 if (Math.random() < arrivalProbability) { numberOfArrivals++; var transactionTime = (int) (Math.random() * maxTransactionTime + 1);//生成每位顾客的服务时间 var customer = new Customer(clock, transactionTime, numberOfArrivals); // 创建到达的顾客 line.enqueue(customer); } // 某位顾客是否还在服务中 if (transactionTimeLeft > 0) { transactionTimeLeft--; //还在服务中,继续服务,不过服务时间要减1 } else { if(!line.isEmpty()) { var nextCustomer = line.dequeue(); // 顾客离开队列,被服务 transactionTimeLeft = nextCustomer.transactionTime - 1; // 赋值服务时间,下次验证是不是在服务他 var waitingTime = clock - nextCustomer.arriveTime; // 每个用户等待服务的时间 totalTimeWaited = totalTimeWaited + waitingTime; // 整个队列中用户等待的时间 numberServed++; } } } }
测试一下
public static void main(String[] args) { WaitLine customerLine = new WaitLine(); customerLine.simulate(20, 0.5, 5); System.out.println(customerLine.numberServed); }
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/34422.html