The queue

Queue is a special kind of linear table. What is special is that it only allows deletion in the front of the table and insertion in the rear of the table. Like stack, queue is a linear table with limited operation. The end that performs the insert operation is called the tail of the queue, and the end that performs the delete operation is called the head of the queue.Copy the code

Introduction to the

The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueuing, and removing a queue element from a queue is called dequeuing. Because queues can only be inserted at one end and deleted at the other end, only the earliest elements in the queue can be removed from the queue first. Therefore, queues are also called FIFO -- first in first out (FIFO).Copy the code

Characteristics of the

In a word: First In First Out, First In First OutCopy the code

Hand rolled code

The team

The queue can be added only if it is not fullCopy the code

public void push(int x) {
    if (this.isFull()) {
        System.out.println("The line is full!);
        return;
    }
    this.quere[this.rear] = x;
    this.rear ++;
    System.out.println("【" + x + "】 Get in line!);
}
Copy the code

Out of the team

You must leave the queue if the queue is not emptyCopy the code

public void pop(a) {
    if (this.isEmpty()) {
        System.out.println("The queue is empty!);
        return;
    }
    System.out.println( "Out of line: [" + this.quere[this.front] +"】");
    this.quere[this.front] = 0;
    this.front ++;
}
Copy the code

Complete demo

public class NewQueue{
    // Queue header index
    private int front = 0;
    // End-of-queue index
    private int rear = 0;
    // Queue size
    private int size = 0;
    / / the queue
    private int[] quere;
    public NewQueue (int length) {
        this.quere = new int[length];
        this.size = length;
    }
    /** * Whether the queue is empty *@return* /
    public boolean isEmpty(a) {
        return this.front == this.rear;
    }
    /** * Whether the queue is full *@return* /
    public boolean isFull(a) {
        return this.rear == this.size - 1;
    }
    /** * Join the team */
    public void push(int x) {
        if (this.isFull()) {
            System.out.println("The line is full!);
            return;
        }
        this.quere[this.rear] = x;
        this.rear ++;
        System.out.println("【" + x + "】 Get in line!);
    }
    /** * out of team */
    public void pop(a) {
        if (this.isEmpty()) {
            System.out.println("The queue is empty!);
            return;
        }
        System.out.println( "Out of line: [" + this.quere[this.front] +"】");
        this.quere[this.front] = 0;
        this.front ++;
    }
    /** * Reset queue */
    public void reset(a) {
        for (int i = this.front; i < this.rear; i++) {
            this.quere[i] = 0;
        }
        this.front = 0;
        this.rear = 0;
        System.out.println("Queue reset!");
    }
    /** * Print */
    public void showQueue(a) {
        System.out.println("Print queue!");
        for (int i = this.front; i < this.rear; i++) {
            System.out.print(quere[i] + "");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        NewQueue newQueue = new NewQueue(6);
        newQueue.push(1); // [1] Enter the queue!
        newQueue.push(2); // 【2】 Enter the queue!
        newQueue.pop();   // Out of line: [1]
        newQueue.push(3); // 【3】 Enter the queue!
        newQueue.push(4); // 【4】 Enter the queue!
        newQueue.push(5); // 【5】 Enter the queue!
        newQueue.pop();   // Out of the queue: [2]
        newQueue.showQueue(); // Print the queue! 3, 4, 5
        newQueue.reset(); // Queue reset!}}Copy the code

conclusion

In this paper, the sequential queue is implemented. What really represents the queue is the storage space between the head pointer front and the tail pointer rear. Since the head pointer front and the tail pointer rear change dynamically, when front and rear point to the same position, When rear points to the last position of the defined queue, it means that the queue is full. Even if front does not necessarily appear at the first place of the defined queue, it means that the queue is full. When the queue is full and you add elements to it, it will overflow the queue, but there may be space in front of front, This is called a false overflow.Copy the code

Applicable scenario

The most familiar is the thread pool in Java, and various messaging middlewareCopy the code