[数据结构与算法]数组实现环形链表

一、数组实现环形链表

package com.bear.queue;

/**
 * @author Spring-_-Bear
 * @datetime 2022/3/10 15:43
 */
public class CircleArrayQueue {
   private final int maxSize;
   private final int[] array;
   /**
    * 队列头指针：初始化为 0
    */
   private int front;
   /**
    * 队列尾指针：初始化为 0
    */
   private int rear;

   public CircleArrayQueue(int maxSize) {
      this.maxSize = maxSize;
      this.array = new int[maxSize];
   }

   public boolean isFull() {
      return (rear + 1) % maxSize == front;
   }

   public boolean isEmpty() {
      return front == rear;
   }

   /**
    * 添加数据到队列尾
    *
    * @param data data
    */
   public void add(int data) {
      if (isFull()) {
         System.out.println("队列已满，无法添加数据");
         return;
      }
      array[rear] = data;
      rear = (rear + 1) % maxSize;
   }

   /**
    * 获取队头元素
    *
    * @return data
    */
   public int get() {
      if (isEmpty()) {
         throw new RuntimeException("队列为空，无法取出数据");
      }
      int temp = array[front];
      front = (front + 1) % maxSize;
      return temp;
   }

   /**
    * 打印队列所有有效元素
    */
   public void list() {
      if (isEmpty()) {
         System.out.println("队列为空，无数据");
         return;
      }
      for (int i = front; i < front + dataSize(); i++) {
         int index = i % maxSize;
         System.out.printf("array[%d] = %d\n", index, array[index]);
      }
   }

   /**
    * 取得队头元素
    *
    * @return data
    */
   public int peek() {
      if (isEmpty()) {
         throw new RuntimeException("队列为空，无数据");
      }
      return array[front];
   }

   /**
    * 求出当前队列中的有效数据个数
    *
    * @return count
    */
   public int dataSize() {
      return (rear - front + maxSize) % maxSize;
   }
}

二、实现测试

package com.bear.queue;


import java.util.Scanner;

/**
 * @author Spring-_-Bear
 * @datetime 2022/3/10 15:45
 */
public class CircleArrayQueueTest {
    public static void main(String[] args) {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("s - show");
            System.out.println("a -add");
            System.out.println("g - get");
            System.out.println("p - peek");
            System.out.println("q - quit");
            System.out.print("Please input your choice:");
            String choice = scanner.next();
            switch (choice) {
                case "s":
                    circleArrayQueue.list();
                    break;
                case "a":
                    System.out.print("Input the data you want to add:");
                    int i = scanner.nextInt();
                    circleArrayQueue.add(i);
                    break;
                case "g":
                    System.out.println("The data you get is " + circleArrayQueue.get());
                    break;
                case "p":
                    System.out.println("The peek data is " + circleArrayQueue.peek());
                    break;
                case "q":
                    System.exit(0);
                default:
                    System.out.println("Input error, input again");
                    break;
            }
        }
    }
}