背景 隊列[Queue]：是一種限定僅在表頭進行刪除操作，僅在表尾進行插入操作的線性表；即先進先出（FIFO-first in first out）:最先插入的元素最先出來。 本文通過編碼實現鏈式隊列類，並模擬一個有趣的應用，能夠幫助我們對鏈式隊列有更深度的理解。 基本概念 結點 每個元素，除了存儲 ...
目錄
背景
隊列[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封郵件進入發送隊列；
- 隊列按先進先出順序發送任務：在程式隨機數生成模擬發送時間，並顯示當前發送任務；
- 輸出總共發送任務時長。
結果輸出如下：
