数组实现循环队列_用数组实现循环队列

数组实现循环队列

队列基本概念

就如现实中排队吃饭一样，先排队的人先吃饭，后排队的人后吃饭，队列中遵循先进先出的原则

循环队列示意图

循环队列概念

如果只是用数组来实现队列，而不考虑循环的话，当尾部指针走到数组最大长度时，就无法在添加数据，在循环队列中，当数组中只要还有空余的位置，就能一直进行添加操作，这大大节约了空间。

当rear=0，front=0时（front表示头部，rear表示尾部）

(rear+1)%maxQueue==front时，表示队列已满(maxQueue表示数组能装数据的个数)

rear==front时，队列为空

代码实现

public class Demo03 {
    public static void main(String[] args) {
        arrayQueue queue= new arrayQueue(3);
        Scanner sc=new Scanner(System.in);
        boolean flat=true;  //标志变量
        while (flat){
            System.out.println("a(在队列中添加数据)");
            System.out.println("g(在队列中取出数据)");
            System.out.println("h(查看队列中的头部数据)");
            System.out.println("s(查看队列中的数据)");
            System.out.println("e(退出程序)");
            char s=sc.next().charAt(0);
            switch (s){
                case 'a':{ //用户输入a：在队列中添加数据
                    System.out.println("请输入要添加的数：");
                    int value=sc.nextInt();
                    queue.addQueue(value);
                    break;
                }
                case 'g':{ //用户输入g：在队列中取出数据
                    try{   //try{}catch{}捕获异常
                        int value=queue.getQueue();
                        System.out.println("成功取出数据，取出的数据为："+value);
                        System.out.println("取出成功！！当前队列为：");
                        queue.listQueue();
                    }catch (RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                }
                case 'h':{  //用户输入h：查看队列中的头部数据
                    try{
                        int value=queue.headQueue();
                        System.out.println("当前头部数据为："+value);
                    }catch (RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                }
                case 's':{ //用户输入s: 查看队列中的数据
                    try{
                        queue.listQueue();
                    }catch (RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                }
                case 'e':{  //用户输入e: 退出程序
                    sc.close();
                    flat=false;
                }
            }
        }
    }
    //数组形式实现队列
    static class arrayQueue{
        int maxQueue; //数组长度
        int front; //队列头部
        int rear;  //队列尾部
        int [] arr;
        public  arrayQueue(int maxQueue){
            this.maxQueue=maxQueue;
            arr=new int[maxQueue];
            front=0; //front表示队列头部数据的位置
            rear=0;  //rear表示队列尾部数据后一个的位置
        }

        //判断队列是否为满
        public Boolean isEmpty(){
            return (rear+1)%maxQueue==front;  //当rear+1对maxQueue取模等于front时表示队列已经满了
        }
        //判断队列是否空
        public Boolean isFull(){
            return rear==front;  //队头部与尾部相等时表示队列为空
        }
        //在队列中添加数据
        public void addQueue(int value){
            if(isEmpty()){
                System.out.println("队列已满，不能添加数据！！！");
                return;
            }
            arr[rear++%maxQueue]=value;  //因为rear表示的是当前队列尾部的后一个位置，
                                         //所以在添加时arr[rear]=value即可，但添加过后，rear需要移动位置，所以rear+1.
                                         //只有rear%maxQueue时，才能将数据存入数组相对于的位置
            System.out.println("添加成功！！当前队列为：");
            listQueue();
        }
        //从队列中取出数据
        public int getQueue(){
            if(isFull()){
                throw new RuntimeException("队列为空，无法取出！！！");
            }
            int value=arr[front++%maxQueue]; //front表示队列头部位置，所以先取出在移动位置
            return value;
        }
        //查看队列的头部数据
        public int headQueue() {
            if (isFull()) {
                throw new RuntimeException("队列为空!!!");
            }
            return arr[front%maxQueue];//front表示队列头部位置,所以直接查看即可，查看无须改变front位置
        }
        //打印队列
        public void listQueue(){
            if(isFull()){
                throw new RuntimeException("队列为空!!!");
            }
            System.out.println("当前队列为：");
            for (int i = front; i <rear; i++) {  //front为队列头部位置，所以i赋初值为front，rear为队列尾部的后一个位置，所以i<rear;
                System.out.print(arr[i%maxQueue]+" ");
            }
            System.out.println();
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

点击查看数组实现队列