Queue introduction
Queue is a special linear table, which only allows deletion at the front of the table and insertion at the back of the table. The position where the deletion operation is performed is called the opposite head, and the position where the insertion operation is performed is called the end of the queue.

characteristic
FIFO first in first out to store data.

Queue implementation is mainly divided into sequential queue and circular queue.

• Sequential queue

To establish a sequential queue structure, a piece of continuous storage space must be allocated statically or dynamically, and two pointers must be set for management, one is the head pointer front and the other is the tail pointer rear.
When initializing the queue, real = front = 0. Each time an element is added, real increases by 1; Each time an element is deleted, the front is incremented by 1. With the addition and deletion operations in turn, the number of queue elements changes, and the storage space occupied by the queue also moves in the space allocated for the queue structure. When the rear increases beyond the allocated continuous space, the queue cannot insert elements, but there is often a large amount of available space unoccupied. These spaces are the storage units once occupied by queue elements that have been out of the queue.
Overflow of sequential queue:
1) "Underflow" phenomenon: when the queue is empty, the overflow phenomenon caused by queue operation is made. "Underflow" is a normal phenomenon, which is often used to control the conditions of escape.
2) "True overflow" phenomenon: when the queue is full, the queue operation generates space overflow. "True overflow" is an error state and should be avoided.
3) "False overflow": the space occupied by the deleted element cannot be reused because the head and tail pointers only increase but not decrease in the queue in and out operations. When the actual number of elements in the queue is less than the size of the storage space, the queue entry operation may not be possible because the tail pointer has reached the upper bound of the storage space. This phenomenon is called "false overflow".

Illustration

Implementation of sequential queue java code array

Click to view the code

/**
 * The data implements the sequential queue, including the basic operations of isFull(), isEmpty(), insert(), remove(), and peekFront().
 * @date 2021/12/24
 */
@Data
@Slf4j
public class SequentialQueue {
    /** Queue maximum */
    private int maxSize;
    /** Array implementation */
    private Object[] queueArray;
    /** Team leader */
    private int front;
    /** Team tail */
    private int rear;

    public SequentialQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
        this.front = 0;
        this.rear = 0;
    }

    /** Is the queue full */
    public boolean isFull() {
        return rear == maxSize;
    }
    /** Is the queue empty */
    public boolean isEmpty() {
        return rear == 0;
    }
    /** Join the team */
    public void insert(Object object) {
        // Is the tail of the queue the maximum
        boolean isFull = this.isFull();
        if (isFull) {
            log.error("Queue full, failed to join.");
        } else {
            queueArray[rear] = object;
            rear++;
        }
    }
    /** Out of line, delete data and move the opposite head back */
    public void remove() {
        if (this.isEmpty()) {
            log.error("Queue is empty, dequeue failed.");
        } else {
            queueArray[front] = null;
            front++;
        }

    }
    /** Out of line, delete data and move the opposite head back */
    public Object peekFront() {
        return this.queueArray[front];
    }

    public static void main(String[] args) {
        SequentialQueue queue = new SequentialQueue(3);
        queue.insert(10);
        queue.insert(23);
        queue.insert(34);
        log.info("After joining the team, num = {}", queue.peekFront());
        queue.remove();
        log.info("After leaving the team, num = {}", queue.peekFront());
    }
}

• Circular queue

In the actual use of queues, in order to reuse the queue space, the use method of queues is often slightly improved. Regardless of the insert or delete operation, once the real pointer or front pointer increases by 1 and exceeds the allocated storage space, let them point to the starting position of the storage space. The pointer increases from maxSize-1 to 0, which can be realized by the remainder operations Real% maxsize and front%maxSize.
In fact, the queue space is imagined as a ring space, and the storage units in the space are recycled. The queue managed in this way is a circular queue. In addition to some simple applications, the real practical queue is circular queue.
Illustration

Java data implementation of circular queue

Click to view the code

/**
 * Array implements circular queue, including insert(), remove(), peekFront(), isFull() and isEmpty() methods.
 * @author Yoko
 */
@Data
@Slf4j
public class LoopQueue {
    /** Team leader */
    private int front;
    /** Team tail */
    private int rear;
    /** Implementation array */
    private Object[] queueArray;
    /** Array length */
    private int maxSize;
    /** Actual data volume */
    private int nItem;

    public LoopQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
        this.front = 0;
        this.rear = 0;
        this.nItem = 0;
    }

    /** Is the queue empty */
    public boolean isEmpty() {
        return this.nItem == 0;
    }
    /** Is the queue full */
    public boolean isFull() {
        return this.nItem == this.maxSize;
    }
    /** Join the team */
    public void insert(Object object) {
        if (this.isFull()) {
            log.info("Queue full, failed to join.");
        } else {
            this.queueArray[rear] = object;
            this.rear = (this.rear + 1) % this.maxSize;
            this.nItem++;
        }
    }
    /** Out of the team */
    public void remove() {
        if (this.isEmpty()) {
            log.info("Queue is empty, dequeue failed.");
        } else {
            this.queueArray[front] = null;
            this.front = (this.front + 1) % this.maxSize;
            this.nItem--;
        }
    }
    /** View the value of the queue head */
    public Object peekFront() {
        if (!this.isEmpty()) {
            return this.queueArray[front];
        }
        return null;
    }

    public static void main(String[] args) {
        LoopQueue queue = new LoopQueue(4);
        queue.insert(155);
        queue.insert(10);
        queue.insert(2);
        log.info("Data after joining the team: loopArray = {}", queue);
        log.info("Header value: front= {}", queue.peekFront());

        queue.remove();
        log.info("After leaving the team, queueArray = {}", queue);
        log.info("After leaving the team, the value of the opposite head: front= {}", queue.peekFront());
        queue.insert(223);
        queue.insert(15);
        queue.insert(190);
        log.info("Data after joining the team again: loopArray = {}", queue);
    }
}