数据结构之链式队列的代码实现及有趣应用
2020-05-29 16:05:34来源:博客园 阅读 ()
数据结构之链式队列的代码实现及有趣应用
目录
- 背景
- 基本概念
- 结点
- 代码实现
- 链式队列
- 代码实现
- 链式队列的应用
- 代码分析
背景
队列[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封邮件进入发送队列;
- 队列按先进先出顺序发送任务:在程序随机数生成模拟发送时间,并显示当前发送任务;
- 输出总共发送任务时长。
结果输出如下:
?
?
原文链接:https://www.cnblogs.com/zhuhuix/p/12989710.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:JDK动态代理
- 一口气说出 6种 延时队列的实现方案,面试稳稳的 2020-06-08
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- RedisTemplate实现消息队列并且批量插入数据。 2020-05-22
- 分布式消息队列选型分析 2020-05-19
- Mockito如何mock一条链式调用 2020-05-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash