数据结构与算法（一）：队列

发表于 | 分类于
字数统计: 1.4k

一、什么是队列

队列是一种特殊的线性表。

队列元素的进出遵循“先进先出”原则：即只允许在前端（front）也就是队头进行删除操作，而只能在后端（rear）也就是队尾进行插入操作。

如图所示：

  • 队列的最大长度为MaxSize，最大下标为MaxSize-1
  • 入队时队头下标不变而队尾下标改变，出队时则相反

二、模拟队列

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
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
/**
 * @Author：huang
 * @Date：2020-06-11 16:28
 * @Description：用数组模拟队列
 */
public class Queue {

    //队列最大长度
    private int maxSize;
    //存放数据的数组
    private Object[] arr;
    //头指针，指向队头的元素的前一个位置
    private int front;
    //尾指针，指向队尾的元素所在位置
    private int rear;

    //构造器
    public Queue(int size) {
        this.maxSize = size;
        this.arr = new Object[maxSize];
        this.front = -1;
        this.rear = -1;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        //当头指针和尾指针相等时队列为空
        return rear == front;
    }

    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull(){
        //当尾指针等于maxSize-1时队列满
        return rear == maxSize - 1;
    }

    /**
     * 入队
     * @param item 入队元素
     * @return
     */
    public int addQueue(Object item) {
        //判断队列是否已满
        if (isFull()) {
            throw new RuntimeException("队列已满！");
        }
        //尾指针后移
        rear++;
        arr[rear] = item;
        return rear;
    }

    /**
     * 出队
     * @return
     */
    public Object quitQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空！");
        }
        //头指针后移
        front++;
        return arr[front];
    }

}

2.解决“内存溢出”

咋一眼看上去没问题，但是实际上随着入队和出队操作，头指针和尾指针会不断后移，最后都到达maxSize-1的位置，此时即使实际上有空闲空间也无法往里面添加数据了。

如果要解决这个问题，可以这样改进：

当入队的时候进行一次判断，如果尾指针已经移动到maxSize-1的位置，并且头指针不在-1位置，也就是队列仍然还有空位，就触发一次数据迁移。

打个比方，如果队列长度为6，现在头指针在3，尾指针在5，触发数据迁移后下标3-5的数据移动到0-2去，然后把头指针移到0，尾指针移到2。

基于这个逻辑，只需要改变一下addQueue()入队方法即可：

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
/**
 * 入队
 * @param item 入队元素
 * @return
 */
public int addQueue(Object item) {
    //判断队列是已满还是只是尾指针到头
    if (isFull()) {
        //队列已满
        if (front == -1){
            throw new RuntimeException("队列已满！");
        }else {
            //尾指针到头，触发数据迁移
            for (int i = front; i < rear; i++) {
                arr[i - front] = arr[i];
            }
            //移动指针
            rear = rear - front;
            front = -1;
        }
    }
    //尾指针后移
    rear++;
    arr[rear] = item;
    return rear;
}

虽然问题解决了，但是频繁的移动数据会消耗性能，为此仍需要加以改进：

当尾指针到头以后，如果头指针前还有空闲空间，尾指针应当能移动到头指针之前的位置，也就是队头元素出队了，空出的空间将可以放在队尾被元素入队。

打个比方，就相当于原本的队列是一条直线，走到头就没了，现在要把头和尾连接到一起，让它变成循环队列。

三、循环队列

对于循环队列，有两个问题需要考虑，一个是下标，另一个是队空和队满的判断条件

1.环形队列的下标计算

由于队头元素出队后空间即用于队尾元素入队，所以很可能出现长度5的队列，头指针在1，尾指针在4，这个时候在按照原来的思路用rear+1去入队就会下标越界，因此需要进行取余操作，也就是（rear+1）% maxSize，这样获取下标的问题就解决了。

2.环形队列的状态判断

由于队列变为环形，所以front=rear即可能是队满也可能是队空，针对这个问题有两种思路：

第一种是添加一个变量来记录队列中元素的数量，以区分front=rear时是队满还队空；

第二种是在rear后预留一个空位，通过计算判断rear+1后是否等于front以判断队满还是队空；

这里先用第二种来实现一下：

  • 队空的时候就是front=rear

  • 队满的时候就是rear+1=front，考虑到多次操作后指针可能跑了不止一圈，rear和front可能会大于maxSize，故也需要进行取余操作，所以正确的公式是

    (rear+1)%maxSize = front%maxSize

3.代码实现

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
/**
 * @Author：huang
 * @Date：2020-06-14 16:13
 * @Description：环形队列
 */
public class CricleQueue {

    //队列最大长度
    private int maxSize;
    //存放数据的数组
    private Object[] arr;
    //头指针，指向队头的元素的位置
    private int front;
    //尾指针，指向队尾的元素的位置
    private int rear;

    public CricleQueue(int maxSize) {
        //由于需要在尾指针后空一位作为队满队空的区分，所以实际大小是maxSize+1
        this.maxSize = maxSize + 1;
        this.arr = new Object[maxSize + 1];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        //当头指针和尾指针相等时队列为空
        return rear == front;
    }

    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull(){
        //头尾指针+1并取余时相等时队列满
        return (rear + 1) % maxSize == front;
    }

    /**
     * 入队
     * @param item
     */
    public void addQueue(Object item) {
        if (isFull()){
            throw new RuntimeException("队列已满！");
        }
        arr[rear] = item;
        rear = (rear + 1) % maxSize;
    }
    
	/**
     * 出队
     * @return
     */
    public Object quitQueue() {
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        Object item = arr[front];
        front = (front + 1) % maxSize;
        return item;
    }

}
0%