使用数组实现顺序队列

  1/**
  2 * 使用数组实现一个固定容量的顺序队列。
  3 *
  4 * @author wangy
  5 * @version 1.0
  6 * @date 2021/6/28 / 15:09
  7 */
  8public class ArrayQueue {
  9
 10    private final int[] data;
 11    // cap of data array
 12    private final 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         当tail = cap且head=0，即认为队列"已满"：
 26         ===================================================
 27         data[0]                                   data[7]
 28         |  14  |  8  |  5  |  6  |  9  |  16  |  87  |  67  |
 29           head                                                 tail
 30         ===================================================
 31
 32         当head = tail时，元素都已出队，此时队列为空：
 33         ===================================================
 34         data[0]                                   data[7]
 35         |    |    |     |     |     |      |      |     |
 36                                       head
 37                                       tail
 38         ===================================================
 39
 40         特殊地，当tail = cap且head != 0时，数组明明有空间，元素却无法入队，
 41         这时候就需要将head-tail指针重新整理了：
 42         =======================================================
 43         data[0]                                   data[7]
 44         |    |    |     |     |     |  18  |  34  |  45  |
 45                                       head                 tail
 46         ======================================================================
 47           |  |            data[0]                                     data[7]
 48            \  \---\¯\     | 18  |  34  |  45  |     |     |     |      |     |
 49             \  \--/_/      head                 tail
 50                         ======================================================
 51      */
 52    // index of tail
 53    private int tail;
 54
 55    public ArrayQueue(int cap) {
 56        this.data = new int[cap];
 57        this.cap = cap;
 58        head = tail = 0;
 59    }
 60
 61
 62    int getHead() {
 63        if (isEmpty()) return -1;
 64        return data[head];
 65    }
 66
 67    int getTail() {
 68        if (isEmpty()) return -1;
 69        return data[tail - 1];
 70    }
 71
 72    boolean isFull() {
 73        return tail == cap && head == 0;
 74    }
 75
 76    boolean isEmpty() {
 77        return head == tail;
 78    }
 79
 80    boolean reposition() {
 81        return tail == cap && head != 0;
 82    }
 83
 84    // 入队
 85    int enQueue(int e) {
 86        // full
 87        if (isFull()) throw new ArrayStoreException("队列满了");
 88        // 整理元素
 89        if (reposition()) {
 90            for (int i = head; i < tail; i++) {
 91                data[i - head] = data[i];
 92                data[i] = 0;
 93            }
 94            tail -= head;
 95            head = 0;
 96        }
 97        data[tail++] = e;
 98        return e;
 99    }
100
101    // 出队
102    int deQueue() {
103        // empty
104        if (isEmpty()) throw new ArrayStoreException("队列为空");
105        return data[head++];
106    }
107
108
109    // 打印数组/队列
110    void printAll() {
111        System.out.println("数组：" + Arrays.toString(data));
112        System.out.print("队列：[");
113        if (!isEmpty()) {
114            //
115            for (int i = head; i < tail; i++) {
116                if (i == tail - 1)
117                    System.out.print(data[i]);
118                else
119                    System.out.print(data[i] + ", ");
120            }
121        }
122        System.out.println("]");
123    }
124
125    public static void main(String[] args) {
126        ArrayQueue aq = new ArrayQueue(3);
127        aq.enQueue(1);
128        System.out.println(aq.deQueue());
129        aq.enQueue(2);
130        aq.enQueue(3);
131        aq.enQueue(4);
132
133        System.out.println(aq.deQueue());
134        System.out.println(aq.deQueue());
135        // System.out.println(aq.deQueue());
136
137        System.out.printf("队列头尾索引和值：%s: %s, %s: %s%n",
138                aq.head,
139                aq.getHead(),
140                aq.tail,
141                aq.getTail());
142        aq.printAll();
143    }
144}