当前位置:网站首页>Advanced version of array simulation queue - ring queue (real queuing)

Advanced version of array simulation queue - ring queue (real queuing)

2022-04-23 15:01:00 Wang Yufan

Array to simulate a circular queue ( The real sense of queuing )

Yesterday we did the basic scenario of array simulation queue . You can queue and fetch data ( The first people left the queue ), But we found that , The place taken out cannot be reused . Let's make our queue a one-time queue . Today, let's look at how to improve our queue to be called array simulation ring queue . Realize the reuse of released positions

The basic principle :

You should know that the basic of our queue implementation is the head and tail .rear and front. The direction of these two determines the head and tail of the queue . That is, the queue itself . This specifically refers to the index of the header itself or the previous one and the latter one are not fixed . It depends on the specific algorithm . This time we specify that the head and tail point to by default 0 Indexes .

Optimize the simulation queue of the previous array , Make full use of arrays . So think of the array as a ring .( It can be realized by taking the mold )

Analysis description :

1: When the next index of the tail index is the header index, it means that the queue is full , Upcoming team Empty one column capacity as a convention , This is making a judgment. The queue is full You need to pay attention to (rear + 1) % maxSize == front full ]

2:rear == front [ empty ]

The code is as follows :

package com.joseph.sparseArray;

import java.util.Map;
import java.util.Scanner;

public class CircularQueue {
    public static void main(String[] args) {

            CQueue cQueue = new CQueue(5);
            Scanner sc = new Scanner(System.in);
        int i;
            while(true) {
                System.out.println("--------------- Queuing system --------------");
                System.out.println("---------------1: Queue up for consultation --------------");
                System.out.println("---------------2: End the queue ( The first to succeed )--------------");
                System.out.println("-------------- 3: View the current queue details --------------");
                System.out.println("---------------88:SHOW REAR AND FRONT");
                System.out.println("---------------4: sign out --------------");
                i = sc.nextInt();
                switch (i) {

                    case 1:
                        System.out.println(" Please enter your phone number ");
                        int tel = sc.nextInt();
                        cQueue.add(tel);
                        if(cQueue.rear == 0){
                            if(cQueue.arr[cQueue.MaxSize-1] == tel) {
                                System.out.println(" Queue succeeded !");
                                System.out.println(" The person who has finished queuing first . The current free location is :" + ((cQueue.MaxSize - 1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
                            }
                        }else if (cQueue.arr[cQueue.rear - 1] == tel) {
                            System.out.println(" Queue succeeded !");
                            System.out.println(" The person who has finished queuing first . The current free location is :" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
                            break;
                        } else {
                            System.out.println(" Queue failure !");
                            System.out.println(" The person who has finished queuing first . The current free location is :" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
                            break;
                        }
                    case 2:
                        int oldFront = cQueue.front;
                        cQueue.get();
                        if (cQueue.front != oldFront) {
                            System.out.println(" The person who has finished queuing first . The current free location is :" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
                            break;
                        }
                        System.out.println(" End failure ");
                        break;
                    case 3:
                        cQueue.List();
                        break;
                    case 4:
                        System.out.println(" Thank you for using. !");
                        break;
                    case 88:
                        System.out.println("front:" + cQueue.front);
                        System.out.println("rear:"+cQueue.rear);
                }
            }
    }
}
class CQueue{
    int MaxSize ;// Maximum capacity of array , Because of our REAR( The tail ) It points to the last data index . This means that our real storage length is longer than MaxSize A little one . Because there is always a room for rear Point to . It's an agreement . I said before .
    int rear ;// The tail . Point to the next location of the last data in the queue 
    int front ;// Head . Direct to the first data index subscript 
    int arr[] ;// Array 
    public CQueue(int MaxSize){// Basically unchanged .rear and front The initial value is different from last time . I don't know how to look at the basic version of array simulation queue last time 
        this.MaxSize = MaxSize ;
        arr = new int[MaxSize];
        this.rear = 0;
        this.front = 0;
    }
    public boolean isFull(){
        return (rear+1)%MaxSize == front ;// Because of the ring queue , In fact, the queue is full . It's the difference between them " One ", because rear It points to the last... Of the data . and front The first data pointed to . Because it's a ring ,0 and 4 To connect, there is only one difference. You need to take a mold . utilize rear+1 and MaxSize modulus . be equal to front It means full . This needs to be well understood . It's more difficult 
    }
    public boolean isEmpty(){// The judgment is empty . When they are equal . No matter where . It means there is no data .
        return rear == front ;
    }

    public void add(int key){// Add data 
        if(isFull()){
            System.out.println("QUEUE IS FULL,CAN'T ADD ANYTHING");
            return ;
        }
        arr[rear] = key ;// Direct will rear Subscript assignment of .
        rear = (rear+1)%MaxSize ;// There can be no more self growth here . Because it's circular . Need to use +1 After taking the mold, realize the periodicity . Otherwise, the subscript will cross the boundary 
    }
    public int get(){
        if(isEmpty()){
            throw new RuntimeException("QUEUE IS EMPTY,NO THINGS BE GETED");
        }
        int temp = arr[front] ;// Let's take out the header data first . Put it in temp
        front = (front+1)%MaxSize ;// to front displacement . When the data is taken out . Just back +1 As the initial first data . But it's circular . Keep using +1 After taking the mold, realize the periodicity +1. Otherwise, the subscript will cross the boundary 
        return temp ;
    }
    public void List(){
        // Judge 
        if(isEmpty()){
            System.out.println("QUEUE IS EMPTY!");
            return ;
        }
        for(int i = front ; i < (rear - front + MaxSize)%MaxSize +front ;i++){// We can't use traditional thinking to output . From you to front Start to output . That is, the beginning of the queue 
            // and i The scope of the . No longer queue length . But the number of valid data in the queue +front. It was calculated to be (rear-front+MaxSize)%MaxSize, Actually rear It's the last one of the last data , and front It's the first one . In my submission rear-front Is the number of valid data . And because of the ring . Often negative numbers . So continue to take the mold to achieve the effect of absolute value . Because we are circular .front The initial position will change due to user removal . So we must add front. because front That's where it starts . Plus the number of valid data . Namely i The scope of the 
            System.out.printf(" Team No [%d] Number  : %d\n",i%MaxSize,arr[i%MaxSize]);// The output here is printf Method to make a format . Out-of-service i, To take a mold . Otherwise you cross the line 
        }
    }
}
/**
 * @author JosephWang
 * @date 2021/8/10 11:58
 */

版权声明
本文为[Wang Yufan]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231414327282.html