目录

队列(环形数组实现方式)

环形数组队列

队列的特性是先入先出,也就是在尾部插入数据,在头部删除数据,本文介绍用环形数组实现的队列,如下图所示:

https://gitee.com/lienhui68/picStore/raw/master/null/20200616100958.png

队列的方法主要是增删查,如下接口定义

 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.eh.ftd.dsa.ds;

/**
 * 自定义队列
 *
 * @author David Li
 * @create 2020/06/16 09:50
 */
public interface Queue<T> {
    /**
     * 入队
     *
     * @param t
     * @return
     */
    boolean offer(T t);

    /**
     * 出队
     *
     * @return
     */
    T poll();

    /**
     * 返回队首元素
     *
     * @return
     */
    T peek();

    /**
     * 元素个数
     *
     * @return
     */
    int size();

    /**
     * 是否为空
     *
     * @return
     */
    boolean isEmpty();

    /**
     * 是否为满
     *
     * @return
     */
    boolean isFull();

    /**
     * 展示所有元素
     */
    void display();

}


处理思路

  1. 当队列为空时,head=0;rear==0;
  2. 数组的最后一个元素不存储数据,这样当head==rear表示队列为空,(rear+1)%n==head 表示队列为满 why?:队列中元素的个数是0,1,2,… ,n 共n+1种可能性,但是使用|rear-head|表示是0,1,2,…,n-1 共n种结果,所以必然有两种可能性|rear-head|的结果是一样。我们也可以找出来: https://gitee.com/lienhui68/picStore/raw/master/null/WX20200616-121359@2x.png 如上图2所示这个队列已满,当一直取元素直至head指向第2个元素,此时rear==head, 按照|rear-head|==0那么表示这个队列为空,但此时队列不为空。所以我们使用一个空的数据位来实现循环队列,也就是数组的最后一个元素不保存数据。

代码实现

  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
117
118
119
120
121
122
123
124
125
126
127
128
package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Queue;

import java.util.Scanner;

/**
 * 环形队列
 *
 * @author David Li
 * @create 2020/06/11 18:26
 */

public class CircleQueue<T> implements Queue<T> {

    /**
     * 容量
     */
    private int capacity;

    /**
     * 队首
     */
    private int head;
    /**
     * 队尾
     */
    private int rear;

    private Object[] arr;

    public CircleQueue(int capacity) {
        // 这里因为要空出一个元素,所以需在用户输入元素个数基础上+1
        this.capacity = capacity + 1;
        arr = new Object[capacity + 1];
    }

    @Override
    public boolean offer(T t) {
        if (isFull()) {
            System.out.println("队列已满");
            return false;
        }
        // 直接将数据加入
        arr[rear] = t;
        // 尾指针后移一位,注意取模
        rear = (rear + 1) % capacity;
        return true;
    }

    @Override
    public T poll() {
        if (isEmpty()) {
            return null;
        }
        // 取出元素
        T t = (T) arr[head];
        // front指针后移,注意取模
        head = (head + 1) % capacity;
        return t;
    }

    @Override
    public T peek() {
        return (T) arr[head];
    }

    @Override
    public int size() {
        return (rear - head + capacity) % capacity;
    }

    @Override
    public boolean isEmpty() {
        return head == rear;
    }

    @Override
    public boolean isFull() {
        return (rear + 1) % capacity == head;
    }

    @Override
    public void display() {
        System.out.print("队列: ");
        for (int i = head; i < head + size(); i++) {
            i = i % capacity; // i有可能超出,所以要取模
            System.out.printf("arr[" + i + "]=" + arr[i] + ";\t");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        // 创建一个队列
        Queue<Integer> queue = new CircleQueue<>(5);
        Scanner scanner = new Scanner(System.in);
        // 定义一个字符用来接收控制台输入
        char c;
        // 是否退出程序
        boolean loop = true;
        while (loop) {
            System.out.printf("s:展示队列\ta:入队\td:出队\tp:查看队首元素\te:退出程序\n");
            c = scanner.next().charAt(0);
            switch (c) {
                case 's':
                    queue.display();
                    break;
                case 'a':
                    System.out.print("输入一个数:");
                    int num = scanner.nextInt();
                    queue.offer(num);
                    System.out.println();
                    break;
                case 'd':
                    System.out.println("已出队: " + queue.poll());
                    break;
                case 'p':
                    System.out.println("队首元素: " + queue.peek());
                    break;
                case 'e':
                    loop = false;
                    break;
            }
        }
    }
}

运行结果: https://gitee.com/lienhui68/picStore/raw/master/null/20200616112412.png