Java数据结构——环形队列

  1 package com.taru.queue;
  2 
  3 import java.util.Scanner;
  4 
  5 public class CircleQueueDemo {
  6     public static void main(String[] args) {
  7         //测试程序
  8         CircleQueue queue = new CircleQueue(4);
  9         char key = ‘ ‘;//接收用户输入
 10         Scanner scanner = new Scanner(System.in);
 11         boolean loop = true;
 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             System.out.println("h(head):显示队列头部");
 18             key = scanner.next().charAt(0);
 19             switch (key){
 20                 case ‘s‘:
 21                     queue.showQueue();
 22                     break;
 23                 case ‘a‘:
 24                     System.out.println("输入一个数:");
 25                     int value = scanner.nextInt();
 26                     queue.addQueue(value);
 27                     break;
 28                 case ‘g‘:
 29                     try {
 30                         int res = queue.getQueue();
 31                         System.out.println("取出的数据：" +res);
 32                     }catch (Exception e){
 33                         e.printStackTrace();
 34                     }
 35                     break;
 36                 case ‘h‘:
 37                     try {
 38                         int head = queue.headQueue();
 39                         System.out.println("取出的头部数据："+head);
 40                     }catch (Exception e){
 41                         e.printStackTrace();
 42                     }
 43                     break;
 44                 case ‘e‘:
 45                     scanner.close();
 46                     loop = false;
 47                     break;
 48                 default:
 49                     break;
 50             }
 51         }
 52         System.out.println("程序已退出----");
 53     }
 54 }
 55 class CircleQueue{
 56     private int maxSize; //环形队列最大容量
 57     //front指向已变更,指向队列第一个元素
 58     // 初始值front=0
 59     private int front;
 60     //rear指向已变更,指向队列最后一个元素的后一位的元素,该元素约定为空,位置不定,是变化的
 61     //初始值rear=0
 62     private int rear;
 63     private int[] arr;//存储队列数据
 64     public CircleQueue(int arrMaxSize){
 65         maxSize = arrMaxSize;
 66         arr = new int[maxSize];
 67     }
 68     //判断队列已满 (rear+1)%maxSize=front
 69     public boolean isFull(){
 70         return (rear+1)%maxSize==front;
 71     }
 72     //判断队列为空 front = rear
 73     public boolean isEmpty(){
 74         return front ==rear;
 75     }
 76     //队列有效数据个数
 77     public int size(){
 78         return (rear +maxSize -front)%maxSize;
 79     }
 80     //存入数据到队列
 81     public void addQueue(int n){
 82         if (isFull()){
 83             System.out.println("环形队列已满，不能存放数据----");
 84             return;
 85         }
 86         arr[rear] = n;
 87         rear = (rear +1)%maxSize;//当rear等于maxSzie时，rear=0,其不能大于maxSize
 88     }
 89     //从队列取出数据
 90     public int getQueue(){
 91         if (isEmpty()){
 92             throw new RuntimeException("环形队列为空，无法取出数据-----");
 93         }
 94         int value = arr[front];
 95         front = (front +1)%maxSize;
 96         return value;
 97     }
 98     //显示队列所有数据
 99     public void showQueue(){
100         if (isEmpty()){
101             System.out.println("队列为空---");
102             return;
103         }
104         for (int i = front;i<front+size();i++){
105             System.out.printf("arr[%d]=%d",i%maxSize,arr[i%maxSize]);
106             System.out.println();
107         }
108     }
109     //显示队列头部数据
110     public int headQueue(){
111         if (isEmpty()){
112             throw new RuntimeException("队列为空-----");
113         }
114         return arr[front];
115     }
116 }