循环队列的实现方式详解(三种处理方式)_循环队列如何实现

这篇文章提供了判断循环队列是否已满，是否为空，提供了三种处理方式，在这里只是提供给大家一种解决问题的方式；

使用数组的方式实现

循环队列本质是一种队列，具有FIFO的数据结构；
把数组想象成为一个一个环状的空间，就是把存储队列元素从逻辑上看作一个环，成为循环队列；

规定Q表示队列,成员变量front,rear分别表示队头指针和队尾指针，MaxSize表示队列数组的长度

有几个比较重要的操作
初始化时：Q.front == Q.rear =0;
队头指针前进时：(Q.front + 1) % MaxSize;
队尾指针前进时：(Q.rear + 1) % MaxSize;
队列的长度：(Q.rear + MaxSize - Q.front) % MaxSize
其实这几个操作，小伙伴们可以细细品一下，以后做数组循环的相关的问题，手到擒来；

循环队列的队满和队空的判断条件是什么？

显然队空的判断条件时Q.front == Q.rear 这是由初始条件决定的；如果入队的速度快于出队的速度，队尾的指针很快追上队头的指针，可以看到队列满的时候也有Q.front == Q.rear;

为了区分循环队列 队满 还是对空？有三种处理方式：

1. 牺牲一个存储单元来区分队满还是队空，入队时少用一个队列单元，“队头指针在队尾指针的下一个位置作为队满的标志”
   队满的条件：（Q.rear + 1）% MaxSize == Q.front

2. 在循环队列中增设表示元素个数的成员变量(size),
   队空的条件：Q.size == 0
   队满的条件：Q.size == Q.MaxSize
   在编码中，这种方式是比较推荐的，这是因为size成员变量可以使得Q.rear,Q.front成员变量解耦；

3. 增设tag成员变量，用于区分队满还是队空。 tag等于0时，因删除导致的Q.front == Q.rear则是队空，tag等于1时，因为插入导致的Q.front== Q.rear，则为队满

定义队列接口
interface Queue {
        int poll();
        void offer(int e);
}
1
2
3
4
5

牺牲一个元素

static class RecycleQueueV1 implements Queue {
        private final int MAXSIZE;
        private final int[] element;
        private int front = 0,rear = 0;
        public RecycleQueueV1(int length) {
            this.element = new int[length];
            this.MAXSIZE = length;
        }
        @Override
        public int poll() {
            if(this.rear == this.front) {
                throw new RuntimeException("队列为空");
            }
            int res = this.element[this.front];
            this.front = (this.front + 1) % MAXSIZE;
            return res;
        }
        @Override
        public void offer(int e) {
            int next = (this.rear + 1) % MAXSIZE;

            if(next == this.front) {
                throw new RuntimeException("队列已满");
            }
            this.element[this.rear] = e;
            this.rear = next;
        }
    }
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

增设一个元素个数的成员变量

    static class RecycleQueueV2 implements Queue{
        private final int MAXSIZE;
        private final int[] element;
        private int front = 0,rear = 0;
        int size = 0;
        public RecycleQueueV2(int length) {
            this.MAXSIZE = length;
            this.element = new int[length];
        }
        @Override
        public int poll() {
            if(size == 0) {
                throw new RuntimeException("队列为空");
            }
            int res = this.element[this.front];
            this.front = (this.front + 1) % MAXSIZE;
            this.size--;
            return res;
        }

        @Override
        public void offer(int e) {
            if(size == MAXSIZE) {
                throw new RuntimeException("队列已满");
            }
            int next = (this.rear + 1) % MAXSIZE;
            this.element[this.rear] = e;
            this.rear = next;
            this.size++;
        }
    }
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

增设一个tag成员变量

static class RecycleQueueV3 implements Queue{

        private final int MAXSIZE;
        private final int[] element;
        // 初始化front == rear == 0,tag = 0,表示此时队列为null
        private int front = 0,rear = 0;
        int tag = 0;//
        public RecycleQueueV3(int length){
            this.MAXSIZE = length;
            this.element = new int[length];
        }

        @Override
        public int poll() {
            if(tag == 0 && this.front == this.rear) {
                throw new RuntimeException("队列为空");
            }
            int res = this.element[this.front];
            this.front = (this.front + 1) % MAXSIZE;

            if(this.front == this.rear) tag = 0;

            return res;
        }
        @Override
        public void offer(int e) {
            if(tag == 1 && this.front == this.rear) {
                throw new RuntimeException("队列已满");
            }
            int next = (this.rear + 1) % MAXSIZE;
            this.element[this.rear] = e;
            this.rear = next;

            if(this.rear == this.front) tag = 1;

        }
    }
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