資料結構之鏈式佇列的代碼實作及有趣應用

• 背景
• 基本概念
  • 結點
  • 代碼實作
  • 鏈式佇列
  • 代碼實作
• 鏈式佇列的應用
  • 代碼分析

背景

佇列[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 = https://www.cnblogs.com/zhuhuix/p/t;
        this.next = n;
    }

    public T getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node 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 = https://www.cnblogs.com/zhuhuix/p/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) + "毫秒");

    }
}

代碼分析

1. 定義一個郵件類；
2. 建立一個存放郵件發送任務的鏈式佇列；
3. 生成100封郵件進入發送佇列；
4. 佇列按先進先出順序發送任務：在程式亂數生成模擬發送時間，并顯示當前發送任務；
5. 輸出總共發送任務時長，

結果輸出如下：
?

?

標籤：Java

上一篇：Spring08_純注解實戰_支持事務版本

下一篇：JDK動態代理