队列

数组模拟队列实现

思路分析

核心：先进先出，这也是队列应用场景的核心思路。

从代码的角度考虑

  1. 我们需要一个arr[]数组来存储每一个元素
  2. 规定front指向第一个元素的前一个位置，front会随着数据的输出而改变。
  3. 规定rear指向最后一个元素的前一个位置，rear会随着数据的输入而改变。
  4. 当rear == MAXSIZE - 1时，队列满
  5. 当rear == front时，队列为空
  6. enQueue入队操作时
    • 先判断队列是否已满（使用isFull方法）
    • 将尾指针后移++rear, 再入队列
  7. deQueue出队操作时
    • 先判断队列是否为空（使用isEmpty方法）
    • 将头指针后移++front，再出队列
  8. headQueue查看队首元素，不能将使用front+1，不能移动front

最后注意一下可能会抛出异常的方法在调用时，要用try catch包围。

代码实现

ArrayQueue

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
package com.yukinoshita.ArrayQueueDemo;


public class ArrayQueue {
    private int MAXSIZE;
    private int front;//指向队首的前一个位置
    private int rear;//指向队尾
    private int[] arr;

    public ArrayQueue(int size) {
        this.MAXSIZE = size;
        arr = new int[MAXSIZE];
        front = -1;
        rear = -1;
    }

    public boolean isFull() {
        return rear == MAXSIZE - 1;//是队列尾到达MAXSIZE-1,才说明满
    }

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

    public void enQueue(int data) {
        if (isFull()) {
            System.out.println("队列已满");
            return;
        }
        arr[++rear] = data;
        System.out.printf("元素%d已入队\n", data);
    }

    public int deQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[++front];
    }

    //但其实这个方法不应该有
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = front + 1; i <= rear; i++) {
            System.out.printf("%d\t", arr[i]);
        }
        System.out.println();
    }

    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front + 1];
    }
}

ArrayQueueDemo

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
package com.yukinoshita.ArrayQueueDemo;

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char operate = ' ';
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("---------------------");
            System.out.println("e(enQueue)入队：");
            System.out.println("d(deQueue)出队：");
            System.out.println("s(showQueue)展示队列：");
            System.out.println("h(headQueue)展示队列头部：");
            System.out.println("q：退出程序");
            System.out.print("Enter operation: ");
            operate = scanner.next().charAt(0);
            System.out.println("---------------------");

            switch (Character.toLowerCase(operate)) {
                case 'e' -> {
                    System.out.print("输入你要入队的元素：");
                    int data = scanner.nextInt();
                    arrayQueue.enQueue(data);
                }
                case 'd' -> {
                    try {
                        System.out.printf("元素%d已出队\n", arrayQueue.deQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }

                case 's' -> {
                    System.out.println("队列中已有元素为:");
                    arrayQueue.showQueue();
                }
                case 'h' -> {
                    try {
                        System.out.printf("队首元素为%d\n", arrayQueue.headQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }
                case 'q' -> {
                    scanner.close();
                    System.exit(0);
                }
                default -> System.out.println("Invalid operation");
            }

        }
    }
}

上述代码基本实现了一个队列，但是存在问题：数组只能使用一次，不能复用！

数组模拟环形/循环队列实现

思路分析

需充分利用数组空间，则可用取模来实现

  1. 规定front为队首元素，初始值为0
  2. 规定rear为队尾的后一个元素，初始值为0
  3. 采取空余一个空间的方式，当(rear+1)%MAXSIZE == front时，说明队列已满。
  4. 当fornt == rear时，说明队列为空。
  5. enQueue入队列操作
    • 先判断队列是否已满isFull
    • 再插入元素：arr[rear] = data，更新rear：rear = (rear+1)%MAXSIZE
  6. deQueue出队列操作
    • 先判断队列是否为空isEmpty
    • 在出队列：return arr[front]，更新front：front = (front+1)%MAXSIZE
  7. 故，队列中有效数据的个数为：(rear+MAXSIZE-front)%MAXSIZE，不妨增加一个判断有效数据个数的方法

预留一个空间的目的是，方便区分判断队列为空、队列已满的条件。否则，需新增一个变量来辅助判断队列为空还是满。(因为此时rear == front，你不能判断队列是空还是满。)

代码实现

CircleArrayQueue

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
package com.yukinoshita.CircleArrayQueue;


public class CircleArrayQueue {
    private int MAXSIZE;//本代码实现时，空余的一个空间，所以实际有效数据个数为MAXSIZE-1
    private int front;//指向队首
    private int rear;//指向队尾的后一个元素
    private int[] arr;

    public CircleArrayQueue(int size) {
        this.MAXSIZE = size;
        arr = new int[MAXSIZE];
        front = 0;
        rear = 0;
    }

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

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

    public void enQueue(int data) {
        if (isFull()) {
            System.out.println("队列已满");
            return;
        }
        arr[rear] = data;
        rear = (rear + 1) % MAXSIZE;
        System.out.printf("元素%d已入队\n", data);
    }

    public int deQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int data = arr[front];
        front = (front + 1) % MAXSIZE;
        return data;

    }

    //但其实这个方法不应该有
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = front; i < front + this.size(); i++) {
            System.out.printf("%d\t", arr[i % MAXSIZE]);
        }
        System.out.println();
    }

    public int size() {
        return (rear + MAXSIZE - front) % MAXSIZE;
    }

    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }
}

CircleArrayQueueDemo

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
package com.yukinoshita.CircleArrayQueue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
        char operate = ' ';
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("---------------------");
            System.out.println("e(enQueue)入队：");
            System.out.println("d(deQueue)出队：");
            System.out.println("s(showQueue)展示队列：");
            System.out.println("h(headQueue)展示队列头部：");
            System.out.println("q：退出程序");
            System.out.print("Enter operation: ");
            operate = scanner.next().charAt(0);
            System.out.println("---------------------");

            switch (Character.toLowerCase(operate)) {
                case 'e' -> {
                    System.out.print("输入你要入队的元素：");
                    int data = scanner.nextInt();
                    circleArrayQueue.enQueue(data);
                }
                case 'd' -> {
                    try {
                        System.out.printf("元素%d已出队\n", circleArrayQueue.deQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }

                case 's' -> {
                    System.out.println("队列中已有元素为:");
                    circleArrayQueue.showQueue();
                }
                case 'h' -> {
                    try {
                        System.out.printf("队首元素为%d\n", circleArrayQueue.headQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }
                case 'q' -> {
                    scanner.close();
                    System.exit(0);
                }
                default -> System.out.println("Invalid operation");
            }

        }
    }
}