用数组实现自动扩容的无界队列

  1/**
  2 * 使用数组实现无界顺序队列（自动扩容）
  3 *
  4 * @author wangy
  5 * @version 1.0
  6 * @date 2021/6/28 / 17:02
  7 */
  8public class ArrayQueueUnbounded {
  9    private int[] data;
 10
 11    // size of data array
 12    private int cap;
 13    // index of head element
 14    private int head;
 15    /*
 16       关于tail指针，一般是将tail指向最新的可以插入元素的index，
 17       即tail是一个空槽（slot）：
 18       ===================================================
 19        data[0]                                   data[7]
 20        |    |    |  5  |  6  |  9  |  16  |      |     |
 21                   head                      tail
 22       ===================================================
 23        初始化时，head = tail = 0，此后每插入一个元素，tail后移一位。
 24
 25        当head = tail时，认为队列已空，因为tail是一个空槽：
 26        ===================================================
 27        data[0]                                   data[7]
 28        |    |    |     |     |     |     |      |     |
 29                                            tail
 30                                            head
 31        ===================================================
 32
 33        当tail = cap时，即认为队列"已满"：
 34        ========================================================
 35        data[0]                                   data[7]
 36        |    |    |  5  |  6  |  9  |  16  |  87  |  56  |
 37                   head                                    tail
 38        ========================================================
 39
 40        有一个特殊的情况，即 head = tail = cap-1 时，此时队列是空的，也是满的，
 41        不过其不影响队列后续的入队：
 42        ===================================================
 43        data[0]                                   data[7]
 44        |    |    |     |     |     |     |      |     |
 45                                                   tail
 46                                                   head
 47        ===================================================
 48     */
 49    // index of tail element + 1
 50    private int tail;
 51
 52    public ArrayQueueUnbounded() {
 53        // initialization capacity: 4
 54        this.data = new int[4];
 55        this.cap = 4;
 56        this.head = this.tail = 0;
 57    }
 58
 59    boolean isFull() {
 60        // 当tail指向最后一个空槽时，即认为队列已满
 61        return tail == cap ;
 62    }
 63
 64    boolean isEmpty() {
 65        // 无论指针在何处，只要2个指针"相遇"，即认为队列为空
 66        return head == tail;
 67    }
 68
 69    // 入队 平均时间复杂度O(1)
 70    int enQueue(int e) {
 71        // 若队列满了，那么增加容量，并且将队列中的元素进行重排
 72        // |x|x|1|2| => |1|2|-|-|-|-|
 73        if (isFull()) {
 74            cap += cap >> 1;
 75            int[] newData = new int[cap];
 76            for (int i = head; i < tail; i++) {
 77                newData[i - head] = data[i];
 78            }
 79            data = newData;
 80            tail -= head;
 81            head = 0;
 82        }
 83        data[tail++] = e;
 84        return e;
 85    }
 86
 87    // 出队
 88    int deQueue() {
 89        if (isEmpty()) throw new RuntimeException("队列为空！");
 90        return data[head++];
 91    }
 92
 93    // 打印数组/队列
 94    void printAll() {
 95        System.out.println("数组：" + Arrays.toString(data));
 96        System.out.print("队列：[");
 97        if (!isEmpty()) {
 98            for (int i = head; i < tail; i++) {
 99                if (i == tail - 1)
100                    System.out.print(data[i]);
101                else
102                    System.out.print(data[i] + ", ");
103            }
104        }
105        System.out.println("]");
106    }
107
108    public static void main(String[] args) {
109        ArrayQueueUnbounded aqu = new ArrayQueueUnbounded();
110        aqu.enQueue(1);
111        aqu.deQueue();
112        aqu.enQueue(2);
113        aqu.enQueue(3);
114        aqu.enQueue(4);
115        aqu.deQueue();
116        aqu.deQueue();
117        aqu.deQueue();
118//        aqu.deQueue();
119        aqu.enQueue(5);
120        aqu.printAll();
121    }
122}