数组模拟环形队列

图示：

代码：

  1 import java.util.Scanner;
  2 
  3 public class RingQueueTest {
  4     public static void main(String[] args) {
  5         // 创建一个环形队列
  6         RingQueue queue = new RingQueue(7);
  7         // 接收用户输入
  8         char key = ' ';
  9         Scanner scanner = new Scanner(System.in);
 10         boolean loop = true;
 11         // 输出一个菜单
 12         while (loop) {
 13             System.out.println("s(show): 显示队列");
 14             System.out.println("e(exit): 退出程序");
 15             System.out.println("a(add): 添加数据到队列");
 16             System.out.println("g(get): 从队列取出数据");
 17             key = scanner.next().charAt(0);// 接收一个字符
 18             switch (key) {
 19                 case 's':
 20                     System.out.println(queue.toString());
 21                     break;
 22                 case 'a':
 23                     System.out.println("输出一个数");
 24                     int value = scanner.nextInt();
 25                     queue.push(value);
 26                     break;
 27                 case 'g': // 取出数据
 28                     try {
 29                         int res = queue.pop();
 30                         System.out.printf("取出的数据是%d\n", res);
 31                     } catch (Exception e) {
 32                         // TODO: handle exception
 33                         System.out.println(e.getMessage());
 34                     }
 35                     break;
 36                 case 'e': // 退出
 37                     scanner.close();
 38                     loop = false;
 39                     break;
 40                 default:
 41                     break;
 42             }
 43         }
 44         System.out.println("程序退出~~");
 45     }
 46 }
 47 
 48 /**
 49  * 数组模拟环形队列
 50  */
 51 class RingQueue {
 52 
 53     /**
 54      * 指向第一个元素的下标
 55      */
 56     private int front = 0;
 57 
 58     /**
 59      * 指向末尾元素的下一个空位的下标
 60      * 为了区分空数组和满数组的判断条件，指向的空间为预留空间，永不存放元素
 61      */
 62     private int rear = 0;
 63 
 64     /**
 65      * 数组最大长度
 66      * 满数组时元素的个数为maxSize - 1
 67      */
 68     private int maxSize;
 69 
 70     /**
 71      * 存放元素的数组
 72      */
 73     private int[] array;
 74 
 75     public RingQueue(int size) {
 76         //因为有预留空间，所以数组真实长度为size + 1
 77         this.maxSize = size + 1;
 78         this.array = new int[maxSize];
 79     }
 80 
 81     /**
 82      * 判断队列是否为空
 83      * @return
 84      */
 85     public boolean isEmpty() {
 86         return front == rear;
 87     }
 88 
 89     /**
 90      * 判断队列是否为满
 91      * @return
 92      */
 93     public boolean isFull() {
 94         return (rear + 1) % maxSize == front;
 95     }
 96 
 97     /**
 98      * 添加元素
 99      * @param element
100      * @return
101      */
102     public boolean push(int element) {
103         if (isFull()) {
104             System.out.println("队列已满，无法添加元素");
105             return false;
106         }
107         array[rear] = element;
108         rear = (rear + 1) % maxSize;
109         return true;
110     }
111 
112     /**
113      * 弹出元素
114      * @return
115      */
116     public int pop() throws Exception {
117         if (isEmpty()) {
118             throw new Exception("队列为空，无法取出元素");
119         }
120         int result = array[front];
121         front = (front + 1) % maxSize;
122         return result;
123     }
124 
125     /**
126      * 队列中元素的个数
127      * @return
128      */
129     public int size(){
130         return (rear + maxSize - front) % maxSize;
131     }
132 
133     @Override
134     public String toString() {
135         if (isEmpty()) {
136             return "队列为空";
137         }
138         StringBuilder stringBuilder = new StringBuilder();
139         for (int i = front; i < front + size(); i++) {
140             stringBuilder.append(array[i % maxSize]).append(',');
141         }
142         stringBuilder.deleteCharAt(stringBuilder.length() - 1);
143         return stringBuilder.toString();
144     }
145 }