数据结构之链式队列的代码实现及有趣应用
目录
背景
队列[Queue]:是一种限定仅在表头进行删除操作,仅在表尾进行插入操作的线性表;即先进先出(FIFO-first in first out):最先插入的元素最先出来。
本文通过编码实现链式队列类,并模拟一个有趣的应用,能够帮助我们对链式队列有更深度的理解。
基本概念
结点
每个元素,除了存储其本身的信息(数据域)之外,还需存储一个指示其直接后继存放位置的指针。这两部分信息组成数据元素的存储映像,称为结点(Node)。
?
代码实现
/** * 结点类 * * @author zhuhuix * @date 2020-05-29 */ public class Node<T> { // 数据域 private T data; // 指向下一个元素的指针 private Node<T> next; Node(T t, Node<T> n) { this.data = t; this.next = n; } public T getData() { return data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } }
链式队列
- 链式队列是由N个结点组成的;
- 每个队列有且只有一个队头及队尾;
- 入队的结点排在队尾;
- 出队的结点只能是队头的结点。
?
代码实现
- 入队:public void enQueue(T t)
- 出队:public T deQueue()
/** * 链队的实现 * * @author zhuhuix * @date 2020-05-29 */ public class LinkQueue<T> { // 队头元素 private Node<T> front; // 队尾元素 private Node<T> rear; // 队列长度 private Integer length; // 构造方法 public LinkQueue() { this.front = this.rear = null; this.length = 0; } // 入队enQueue public void enQueue(T t) { Node<T> n = new Node<>(t, null); if (this.rear != null) { this.rear.setNext(n); } this.rear = n; if (this.front==null){ this.front=n; } this.length++; } // 出队deQueue public T deQueue() { if (this.length == 0) { return null; } T data = this.front.getData(); this.front = this.front.getNext(); this.length--; return data; } // 查看队头元素 public T peek() { if (this.length == 0) { return null; } T data = this.front.getData(); return data; } //销毁队列 public void destroy() { this.front = null; this.rear = null; this.length = 0; } public Integer getLength() { return length; } }
链式队列的应用
在java开发中,我们经常会遇到需要处理批量任务的时候,如果是用户提交的发送邮件任务,就会形成一个先进先出的邮件队列。我们接下来编写一个Java程序模拟邮件的批量处理。
/** * 链队应用--邮件类 * * @author zhuhuix * @date 2020-05-29 */ public class Mail { // 发件人 private String from; // 收件人 private String to; // 邮件主题 private String subject; // 邮件内容 private String content; // 邮件大小,单位为K private int size; public Mail(String from, String to, String subject, String content, int size) { this.from = from; this.to = to; this.subject = subject; this.content = content; this.size = size; } public String getFrom() { return from; } public void setFrom(String from) { this.from = from; } public String getTo() { return to; } public void setTo(String to) { this.to = to; } public String getSubject() { return subject; } public void setSubject(String subject) { this.subject = subject; } public String getContent() { return content; } public void setContent(String content) { this.content = content; } public int getSize() { return size; } public void setSize(int size) { this.size = size; } }
/** * 链队的应用--模拟批量邮件发送任务 * * @author zhuhuix * @date 2020-05-29 */ public class LinkQueueTest { public static Long id = 0L; public static void main(String[] args) throws InterruptedException { // 定义一个链表队列 LinkQueue<Mail> queue = new LinkQueue<>(); // 模拟将100封需要发送的邮件入列 for(int i=1;i<=100;i++){ queue.enQueue(new Mail("@","@","第"+i+"封邮件","",i)); } // 开始批量发送100封邮件,并统计所有邮件发送的时间 SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS"); Long start = System.currentTimeMillis(); System.out.println("开始时间:" + sdf.format(start)); while(queue.getLength()>0){ // 用随机数模拟发送邮件的时长 Random random = new Random(); TimeUnit.MILLISECONDS.sleep(random.nextInt(1000)); System.out.println("正在发送"+queue.deQueue().getSubject()); } Long end = System.currentTimeMillis(); System.out.println("结束时间:" + sdf.format(end)); System.out.println("耗用了" + (end - start) + "毫秒"); } }
代码分析
- 定义一个邮件类;
- 建立一个存放邮件发送任务的链式队列;
- 生成100封邮件进入发送队列;
- 队列按先进先出顺序发送任务:在程序随机数生成模拟发送时间,并显示当前发送任务;
- 输出总共发送任务时长。
结果输出如下:
?
?
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30