What is a queue

A queue is a linear data structure. Different from the stack with the same linear data structure, the elements in the queue follow the First In First Out rule. Like queuing in reality, it pays attention to the principle of first come, first served. The exit end of the queue is called the front, and the entrance end of the queue is called the rear.

Similar to the stack, the linear data structure of queue can be realized by array or linked list. When using arrays, we can specify the position of the end of the queue by ourselves. For example, we can specify that the next position of the last element is the end of the queue, or we can specify that the position of the last element is the end of the queue. Both of these are OK. After all, we implement them ourselves. This article specifies that the next position of the last element is the tail of the team. At the same time, this paper uses array to realize queue.

The linked list of queues is implemented as follows:

The array of queues is implemented as follows:

We use element 0 for placeholders.

Basic operation of queue

The basic operations of queue include enqueue and dequeue.

1. Join the team

Joining the queue is to put the new element into the queue. It is only allowed to join the queue from the end of the queue. After joining the queue, the position of the next element of the new element is called the end of the queue. For example, if a queue with elements 3, 5, 1, 4, 9 and 6 needs to queue element 7, the new queue after joining is:

2. Out of the team

Out of the queue is to move elements out of the queue from the direction of the team head. Out of the queue operation is only allowed on the side of the team head. After leaving the team, a new element of the out of team element is used as the new team head. For example, there is an existing queue with elements 3, 5, 1, 4, 9, 6 and 7. If the queue header element 3 needs to be dequeued, the new queue will be:

Obviously, in the queue out operation, we only moved the direction of the queue head element, but did not delete the original queue head element. In this way, there will be a problem. If we do not delete the original element, we will always carry out the out of queue operation, resulting in the meaningless space on the left of the queue head. If we do not expand the array capacity, The queue capacity will only become smaller and smaller. In view of this situation, there is a special queue - circular queue.

Suppose there is an existing queue with a capacity of 9. After a series of queue in and queue out operations, there are only two elements left. These two elements are located at the penultimate and penultimate positions of the queue, that is, the queue is full, but there is a new element to join the queue. On the premise of not expanding the capacity of the array, we can make the new tail point to the first place of the array, Take advantage of the space in the queued elements. In this way, the elements of the whole queue are cycled. In physical storage, the position of the tail of the team can also be in front of the head of the team. When a new element joins the team again, put it at the first place of the array and move the tail of the team back.

So when do we say the queue is full? According to our regulations, the end of the queue is the position of the last element, that is, when (end of queue subscript + 1)% array length = head of the queue subscript, it means that the queue is full and can no longer be queued Because the tail of the queue always points to the next position of the last element, the maximum capacity of the queue is equal to the length of the array minus 1. The queue is full as follows:

Relevant codes are as follows:

package structure.queue;

/**
 * @ClassName: Queue
 * @Author: jiaomubai
 * @Date: 2022/1/30 14:59
 * @Description:
 */
public class Queue {

    private int[] dataArray;
    private int front;
    private int rear;

    public Queue(int capacity) {
        this.dataArray = new int[capacity];
    }

    public void enQueue(int element) {
        if ((rear + 1) % dataArray.length == front) {
            System.out.println("The team is full");
            System.out.println();
            return;
        }
        dataArray[rear] = element;
        rear = (rear + 1) % dataArray.length;
        System.out.println("After joining the team, the team head element is:" + dataArray[front]);
        System.out.println("After joining the team, the tail element is:" + element);
        System.out.println();
    }

    public int deQueue() {
        if (rear == front) {
            System.out.println("The team is empty");
            System.out.println();
        }
        int deQueueElement = dataArray[front];
        front = (front + 1) % dataArray.length;
        System.out.println("After leaving the team, the team head element is:" + dataArray[front]);
        System.out.println("After leaving the team, the tail element is:" + dataArray[rear - 1]);
        System.out.println();
        return deQueueElement;
    }

    public void print() {
        for (int i = front; i != rear - 1; i = (i + 1) % dataArray.length) {
            System.out.print(dataArray[i] + " --> ");
        }
        System.out.println(dataArray[rear - 1]);
        System.out.println();
    }

    public static void main(String[] args) {
        Queue queue = new Queue(6);
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);
        queue.enQueue(6);
        queue.print();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.print();
        queue.enQueue(6);
        queue.enQueue(7);
        queue.print();
    }

}

The execution result of the above code is: