queue

Application scenario and introduction

• Queue is a sequential list, which can be implemented by array or linked list
• Follow the principle of first in, first out. That is, the data stored in the queue should be taken out first, and the data stored later should be taken out later
• Schematic: (use array to simulate queue schematic)

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-6J4xsKDY-1635813370672)(C:\Users \ Xianfang \ appdata \ roaming \ typora user images \ 1635561488287. PNG)]

• The queue itself has a sequence table. If the array structure is used to store the data of the queue, the declaration of the queue array is shown in the figure below, where maxSize is the maximum capacity of the queue
• Because the output and input of the queue are processed from the front and rear ends respectively, two variables front and rear are required to record the subscripts of the front and rear ends respectively. The front will change with the data output, while the rear will change with the data input, as shown in the figure

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ANUlE3YT-1635813370673)(C:\Users \ Xianfang \ appdata \ roaming \ typora \ typora user images \ 1635561703919. PNG)]

Train of thought analysis

• When we store data into a queue, it is called addQueue. The processing of addQueue needs two steps

  1. Move the tail pointer back to rear+1, when front==rear [null]

  2. If the tail needle rear is less than the maximum subscript maxSize-1 of the queue, store the data in the array element indicated by rear, otherwise the data cannot be stored, rear==maxSize-1 [queue full]

code implementation

package ojbk;

import java.util.Scanner;

/**
 * @author Simulating queues using arrays
 */
public class ArrQueue {
    public static void main(String[] args) {
        /**test*/
        ArrayQueue arrQueue = new ArrayQueue(3);
        char key=' ' ;
        Scanner sc = new Scanner(System.in);
        boolean loop=true;
        while (loop){
            System.out.println("s(show):Show queue");
            System.out.println("e(exit):Exit program");
            System.out.println("a(add):Add data to queue");
            System.out.println("g(get):Fetch data from queue");
            System.out.println("h(head):View queue header data");
            /**Receive a character*/
            key=sc.next().charAt(0);
            switch (key){
                case 's':
                    arrQueue.showQueue();
                    break;
                case 'a':
                    try{
                        System.out.println("Enter a number");
                        int value = sc.nextInt();
                        arrQueue.addQueue(value);
                    }catch (Exception e){

                    }
                    break;
                case 'g':
                    try{
                        int queue = arrQueue.getQueue();
                        System.out.println("The extracted data is:"+queue);
                    }catch (Exception e){

                    }
                    break;
                case 'h':
                    try{
                        int i = arrQueue.headQueue();
                        System.out.println("The header data is:"+i);
                    }catch (Exception e){

                    }

                    break;
                case 'e':
                    loop=false;
                    break;
                default:
                    throw new IllegalStateException("Unexpected value: " + key);
            }

        }

    }
}

/**Use arrays to simulate queues - write an ArrayQeueu*/
class ArrayQueue{
    /**Represents the maximum capacity of the array*/
    private int maxSize;
    /**Queue header pointer*/
    private int front;
    /**End of queue pointer*/
    private int rear;
    /**This array is used to store data and simulate queues*/
    private int[] arr;


    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr=new int[maxSize];
        this.front=-1;
        this.rear=-1;
    }

    /**Determine whether the queue is full*/
    public boolean isFull(){
        return rear==maxSize-1;
    }

    /**Determine whether the queue is empty*/
    public boolean isEmpty(){
        return rear==front;
    }
    /**Add data to queue*/
    public void addQueue(int n){
        /**Determine whether the queue is full*/
        if(isFull()){
            System.out.println("The queue is full and data cannot be added");
            return;
        }
        rear++;
        arr[rear]=n;
    }
    /**Get the data and get out of the queue*/
    public int getQueue(){
        /**Determine whether the queue is empty*/
        if(isEmpty()){
            throw new RuntimeException("The queue is empty and data cannot be retrieved");
        }
        front++;
        return arr[front];

    }

    /**Displays all data for the queue*/
    public void showQueue(){
        //ergodic
        if(isEmpty()){
            System.out.println("The queue is empty and there is no data");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }
    /**The header data of the queue is displayed. Note that it is not taken out*/
    public int headQueue(){
        if(isEmpty()){

            throw new RuntimeException("The queue is empty and there is no data");
        }
        return arr[front+1];
    }
}

Problem analysis and Optimization:

1. That is, when the data is retrieved, the subscript space of the array cannot be reused
2. Use the algorithm to improve this array into a ring array%

Use arrays to simulate ring queues

• The previous array simulates the optimization of the queue and makes full use of the array. Therefore, the array is regarded as a ring (it can be realized by%)
• Analysis description
  1. The next header index of the tail index indicates that the queue is full, that is, the capacity of the queue is vacated as a contract. When judging that the queue is full, you should pay attention to (rear+1)% maxSize==front full
  2. rear==front [empty]
  3. Code demonstration
  4. Imagine the front as a pointer. When the queue is full, take out the header element, and then the new element will be inserted into the header. The pointer moves with the inserted element, which reflects the wonderful function of module taking.
  5. Rear refers to the last reserved space (the purpose is that when the rear is full, the rear can judge whether it is full or empty, that is, if the array length is 3, only two elements can be saved to reserve a space for judgment...). For example, when the queue is full (size+1), the last space is empty, Adding an element at this time will add the element to the last space pointed to by the rear (I don't know why to reserve a space specifically. Those who know can leave a message in the comment area, thank you)

/**
 * @author Simulating queues using arrays
 */
public class ArrQueue {
    public static void main(String[] args) {

        //Test one
        System.out.println("Test array simulation ring queue case~~~");

    // Create a ring queue
    CircleArray queue = new CircleArray(4); //Description set 4, and the maximum valid data of its queue is 3
    char key = ' '; // Receive user input
    Scanner scanner = new Scanner(System.in);//
    boolean loop = true;
    // Output a menu
        while (loop) {
        System.out.println("s(show): Show queue");
        System.out.println("e(exit): Exit program");
        System.out.println("a(add): Add data to queue");
        System.out.println("g(get): Fetch data from queue");
        System.out.println("h(head): View data of queue header");
        key = scanner.next().charAt(0);// Receive a character
        switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'a':
                System.out.println("Output a number");
                int value = scanner.nextInt();
                queue.addQueue(value);
                break;
            case 'g': // Fetch data
                try {
                    int res = queue.getQueue();
                    System.out.printf("The extracted data is%d\n", res);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            case 'h': // View data of queue header
                try {
                    int res = queue.headQueue();
                    System.out.printf("The data in the queue header is%d\n", res);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            case 'e': // sign out
                scanner.close();
                loop = false;
                break;
            default:
                break;
        }
    }
        System.out.println("Program exit~~");
}

}


class CircleArray {
    private int maxSize; // Represents the maximum capacity of the array
    //Adjust the meaning of the front variable: front points to the first element of the queue, that is, arr[front] is the first element of the queue
    //Initial value of front = 0
    private int front;
    //Make an adjustment to the meaning of the rear variable: the rear variable points to the next position of the last element of the queue, because you want to free up a space as a convention
    //Initial value of rear = 0
    private int rear; // Queue tail
    private int[] arr; // This data is used to store data and simulate the queue

    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }

    // Determine whether the queue is full
    public boolean isFull() {
        return (rear  + 1) % maxSize == front;
    }

    // Determine whether the queue is empty
    public boolean isEmpty() {
        return rear == front;
    }

    // Add data to queue
    public void addQueue(int n) {
        // Determine whether the queue is full
        if (isFull()) {
            System.out.println("The queue is full and data cannot be added~");
            return;
        }
        //Add data directly
        arr[rear] = n;
        //Move the rear, and here you must consider taking the mold
        rear = (rear + 1) % maxSize;
    }

    // Get the data of the queue and get out of the queue
    public int getQueue() {
        // Judge whether the queue is empty
        if (isEmpty()) {
            // By throwing an exception
            throw new RuntimeException("The queue is empty and data cannot be retrieved");
        }
        // Here, we need to analyze that front is the first element pointing to the queue
        // 1. First keep the value corresponding to front to a temporary variable
        // 2. Move the front backward and consider taking the mold
        // 3. Return temporarily saved variables
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;

    }

    // Displays all data for the queue
    public void showQueue() {
        // ergodic
        if (isEmpty()) {
            System.out.println("The queue is empty and there is no data~~");
            return;
        }
        // Idea: start traversing from front, and how many elements are traversed
        // Use your head
        for (int i = front; i < front + size() ; i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    // Find the number of valid data in the current queue
    public int size() {
        // rear = 2
        // front = 1
        // maxSize = 3
        return (rear + maxSize - front) % maxSize;
    }

    // The header data of the queue is displayed. Note that it is not taken out
    public int headQueue() {
        // judge
        if (isEmpty()) {
            throw new RuntimeException("The queue is empty and there is no data~~");
        }
        return arr[front];
    }

}