Code implementation and interesting application of chained queue of data structure

catalog

background

Queue: a linear table that restricts deletion only in the header and insertion only at the end of the table; that is, FIFO first in first out: the first element to be inserted comes out first.

This paper implements the chained queue class by coding and simulates an interesting application, which can help us have a deeper understanding of chained queue.

Basic concepts

node

Each element, in addition to storing its own information (data domain), also needs to store a pointer indicating its direct storage location. These two parts of information constitute the storage image of data elements, which is called Node.

code implementation
/**
 * Node class
 *  * @author zhuhuix
 * @date 2020-05-29
 */
public class Node<T> {
    // Data field
    private T data;
    // Pointer to the next element
    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;
    }
}
Chain queue
  • The chain queue is composed of N nodes;
  • Each queue has and has only one head and tail;
  • The entry node is at the end of the line;
  • The exit node can only be the head node.
code implementation
  • Team entry: public void enQueue(T t)
  • Outgoing: public T deQueue()
/**
 * The realization of chain team
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class LinkQueue<T> {
    // Team leader element
    private Node<T> front;
    // Team tail element
    private Node<T> rear;
    // queue length 
    private Integer length;

    // Construction method
    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 out
    public T deQueue() {
        if (this.length == 0) {
            return null;
        }
        T data = this.front.getData();
        this.front = this.front.getNext();
        this.length--;
        return data;
    }

    // View team leader elements
    public T peek() {
        if (this.length == 0) {
            return null;
        }
        T data = this.front.getData();
        return data;
    }

    //Destroy queue
    public void destroy() {
        this.front = null;
        this.rear = null;
        this.length = 0;
    }

    public Integer getLength() {
        return length;
    }
}

Application of chain queue

In java development, we often meet the need to deal with batch tasks. If it is a user submitted mail sending task, it will form a first in first out mail queue. Let's write a java program to simulate the mass processing of mail.

/**
 * Chain application - mail class
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class Mail {
    // From
    private String from;
    // addressee
    private String to;
    // Message subject
    private String subject;
    // Message content
    private String content;
    // Message size in 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;
    }

}

/**
 * Application of chain team -- Simulation of bulk mail sending task
 *
 * @author zhuhuix
 * @date 2020-05-29
 */
public class LinkQueueTest {
    public static Long id = 0L;

    public static void main(String[] args) throws InterruptedException {
        // Define a linked list queue
        LinkQueue<Mail> queue = new LinkQueue<>();
        // Simulate the listing of 100 messages to be sent
        for(int i=1;i<=100;i++){
            queue.enQueue(new Mail("@","@","The first"+i+"Messages","",i));
        }
        // Start to send 100 mails in bulk and count the time of sending all mails
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("Start time:" + sdf.format(start));

        while(queue.getLength()>0){
            // Using random number to simulate the time of sending mail
            Random random = new Random();
            TimeUnit.MILLISECONDS.sleep(random.nextInt(1000));

            System.out.println("Sending"+queue.deQueue().getSubject());
        }

        Long end = System.currentTimeMillis();
        System.out.println("End time:" + sdf.format(end));
        System.out.println("Consumed" + (end - start) + "millisecond");

    }
}

code analysis
  1. Define a mail class;
  2. Establish a chain queue to store mail sending tasks;
  3. Generate 100 mails and enter the sending queue;
  4. The queue sends tasks in first in first out order: generate the simulated sending time in the program random number, and display the current sending task;
  5. Output total send task time.

The result output is as follows:

Tags: Java

Posted on Fri, 29 May 2020 08:47:18 -0700 by feidakila