Array simulation [queue] and [ring queue]_ code implementation

1、 Basic introduction to queue

• A queue is a special kind of linear table , What's special about this is that it's only allowed at the front of the table （front） Delete operation , And at the back end of the table （rear） Insert operation , Like the stack , A queue is a linear table with restricted operations . The end of the insertion operation is called the tail of the queue , The end of the delete operation is called the queue head .

• A queue is a sequence table , It can be realized by array or linked list .

• follow First in, first out Principles . namely : Data stored in the queue first , You have to take it out first . After the deposit to take out after

2、 Array mock queue

• The queue itself has a sequence table , If you use the structure of the array to store the data of the queue , The definition is maxSize Is the maximum capacity of the queue .

• Because the output of the queue 、 Input is processed from the front and back end respectively , So we need two variables front And rear Record the subscripts at the front and back of the queue ,front Will change with data output , and rear It changes with data input

• The condition for judging the queue to be empty is ：front == rear

• The condition for judging that the queue is full is ：rear == maxSize- 1

• The process of putting data on a queue requires two steps

  • Tail pointer rear Move back ：rear + 1,
  • If the tail pointer rear Less than the maximum subscript of the queue maxSize -1, Then store the data in rear In the array element , Otherwise, data cannot be stored .

• The process of taking data out of a queue

  • Put the head pointer front Move backward ：front + 1
  • return front Refers to an array element , That is, the extracted data

• Code implementation

  // Array mock queue 
  public class ArrayQueueDemo {
        
      public static void main(String[] args) {
        
          // Create a queue 
          ArrayQueue arrayQueue = new ArrayQueue(3);
          char key = ' ';
          Scanner scanner = new Scanner(System.in);
          boolean loop = true;
          while (loop) {
        
              System.out.println("s(show)： Show queue ");
              System.out.println("e(exit)： Exit queue ");
              System.out.println("a(add)： Add data to the queue ");
              System.out.println("g(get)： Take data out of the queue ");
              key = scanner.next().charAt(0);
              switch(key){
        
                  case 's':
                      arrayQueue.showQueure();
                      break;
                  case 'a':
                      System.out.println(" Enter a number ：");
                      int value = scanner.nextInt();
                      arrayQueue.addQueue(value);
                      break;
                  case 'g':
                      try {
        
                          int res = arrayQueue.getQueue();
                          System.out.printf(" The data is %d\n",res);
                      } catch (Exception e) {
        
                          System.out.println(e.getMessage());
                      }
                      break;
                  case 'h':
                      try {
        
                          int res = arrayQueue.headQueue();
                          System.out.printf(" The data in the queue header is %d\n",res);
                      } catch (Exception e) {
        
                          e.printStackTrace();
                      }
                      break;
                  case 'e':
                      scanner.close();
                      loop = false;
                      break;
                  default:
                      break;
              }
          }
          System.out.println(" Program exit ");
  
      }
  }
  
  // Use arrays to simulate queues , Write a ArrayQueue class 
  class ArrayQueue {
        
      private int maxSize;  // Represents the maximum capacity of an array 
      private int front; // Queue header 
      private int rear; // Queue tail 
      private int[] arr; // This array is used to store data , Simulation queue 
  
      // The constructor that creates the queue 
      public ArrayQueue(int arrMaxSize) {
        
          maxSize = arrMaxSize;
          arr = new int[maxSize];
          front = -1; // Point to the head of the queue , Analysis shows that front It points to the previous position of the queue head 
          rear = -1; // At the end of the queue , Data pointing to the end of the queue （ That is, the last data in the queue ）
      }
  
      // Determines if the queue is empty 
      public boolean isEmpty() {
        
          return rear == front;
      }
      
      // Determine if the queue is full 
      public boolean isFull() {
        
          return rear == maxSize - 1;
      }
  
      // Add data to the queue 
      public void addQueue(int n) {
        
          // Determine if the queue is full 
          if (isFull()) {
        
              System.out.println(" The queue is full , Can't add data ");
              return;
          }
          rear++; // Give Way rear  Move backward 
          arr[rear] = n;
      }
  
      // Get the data of the queue , Outgoing queue 
      public int getQueue() {
        
          // Determines if the queue is empty 
          if (isEmpty()) {
        
              // By throwing an exception 
              throw new RuntimeException(" The queue is empty , Can't get data ");
          }
          front++; //front Move backward 
          return arr[front];
      }
  
      // Show all data in the queue 
      public void showQueure() {
        
          // Traverse 
          if (isEmpty()) {
        
              System.out.println(" The queue is empty , No data ");
              return;
          }
          for (int i = 0; i < arr.length; i++) {
        
              System.out.printf("arr[%d]=%d\n", i, arr[i]);
          }
      }
  }
  

• Problem analysis and optimization

  • At present, the array cannot be used once , It doesn't achieve the effect of reuse
  • Use the algorithm for this array , Improved to a ring queue 【 modulus ：%】

3、 Array to simulate a circular queue

• 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 :

  • front and rear The definition of can be defined by oneself . As long as the requirements of the ring are met . This is a similar code “ modeling ” The process of , There are many ways , Just implement it ,rear and front The position of can also be changed at will

  • front Make an adjustment to the meaning of the variable ：front Point to the first element of the queue , in other words arr[front] It's the first element of the queue

    • front The initial value of the =0

  • rear Make an adjustment to the meaning of the variable ：rear Point to the last position of the last element in the queue , Because I want to make a space as an agreement

    • rear The initial value of the =0

  • maxSize The maximum number is 3 , In fact, only two can be saved , Because a space is reserved ！！！

  • The condition that the queue is empty is ：rear == front【 empty 】

  • The condition for the queue to be full is ：(rear +1) % maxSize == front【 full 】

  • When analyzed as above , The number of valid data in the queue is ： (rear + maxSize - front) % maxSize

  • You can modify the original queue to get a ring queue

• Code implementation

  // Array to simulate a circular queue 
  public class CircleArrayQueueDemo {
        
      public static void main(String[] args) {
        
          System.out.println(" Test array simulation ring queue case ");
          CircleArray arrayQueue = new CircleArray(4);// Description settings 4, The maximum valid data of its queue is 3
          char key = ' '; 
          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 queue ");
              System.out.println("a(add)： Add data to the queue ");
              System.out.println("g(get)： Take data out of the queue ");
              System.out.println("h(head： View the data of the queue header ");
              key = scanner.next().charAt(0); 
              switch(key){
        
                  case 's':
                      arrayQueue.showQueure();
                      break;
                  case 'a':
                      System.out.println(" Enter a number ：");
                      int value = scanner.nextInt();
                      arrayQueue.addQueue(value);
                      break;
                  case 'g':
                      try {
        
                          int res = arrayQueue.getQueue();
                          System.out.printf(" The data is %d\n",res);
                      } catch (Exception e) {
        
                          System.out.println(e.getMessage());
                      }
                      break;
                  case 'h':
                      try {
        
                          int res = arrayQueue.headQueue();
                          System.out.printf(" The data in the queue header is %d\n",res);
                      } catch (Exception e) {
        
                          e.printStackTrace();
                      }
                      break;
                  case 'e':
                      scanner.close();
                      loop = false;
                      break;
                  default:
                      break;
              }
          }
          System.out.println(" Program exit ");
  
      }
  }
  
  class CircleArray{
        
      
      private int maxSize;  // Represents the maximum capacity of an array 
      //front Make an adjustment to the meaning of the variable ：front Point to the first element of the queue , in other words arr[front] It's the first element of the queue 
      //front The initial value of the =0
      
      private int front; // Queue header , The default is 0
      //rear Make an adjustment to the meaning of the variable ：rear Point to the last position of the last element in the queue . Because I want to make a space as an agreement 
      //rear The initial value of the =0
      private int rear; // Queue tail , The default is 0
      private int[] arr; // This array is used to store data , Simulation queue 
  
      public CircleArray(int arrMaxSize){
        
          maxSize = arrMaxSize;
          arr = new int[maxSize];
      }
      
       // Determines if the queue is empty 
      public boolean isEmpty() {
        
          return rear == front;
      }
      
      // Determine if the queue is full 
      public boolean isFull() {
        
          return (rear + 1) % maxSize == front;
      }
  
      // Add data to the queue 
      public void addQueue(int n) {
        
          // Determine if the queue is full 
          if (isFull()) {
        
              System.out.println(" The queue is full , Can't add data ");
              return;
          }
          arr[rear] = n;
          // take rear Move backward , We have to consider taking the mold here 
          rear = (rear + 1) % maxSize;
      }
  
      // Get the data of the queue , Outgoing queue 
      public int getQueue() {
        
          // Determines if the queue is empty 
          if (isEmpty()) {
        
              // By throwing an exception 
              throw new RuntimeException(" The queue is empty , Can't get data ");
          }
          // Here we need to analyze front Is the first element pointing to the queue 
          //1. The first front The corresponding value is kept in a temporary variable 
          //2. take front Move backward , Consider taking the mold 
          //3. Return the temporarily saved variable to 
          int value = arr[front];
          front = (front + 1) % maxSize;
          return value;
      }
  
      // Show all data in the queue 
      public void showQueure() {
        
          // Traverse 
          if (isEmpty()) {
        
              System.out.println(" The queue is empty , No data ");
              return;
          }
          // Ideas ： from front To traverse the , How many elements to traverse 
          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() {
        
          return (rear + maxSize -front) % maxSize;
      }
  
      // Display the header data of the queue , Be careful not to take out the data 
      public int headQueue() {
        
          // Judge 
          if (isEmpty()) {
        
              throw new RuntimeException(" The queue is empty , No data ");
          }
          return arr[front];
      }
  }