JAVA基础算法（8）----- 设计循环双端队列

​​​​​

​ 设计循环双端队列 ​
​

活动地址：CSDN21天学习挑战赛

一、题目

标题：设计实现双端队列。
实现 MyCircularDeque 类:
MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：
输入
[“MyCircularDeque”, “insertLast”, “insertLast”, “insertFront”, “insertFront”, “getRear”, “isFull”, “deleteLast”, “insertFront”, “getFront”]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4

二、解题

• 循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
• 在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。
• 循环队列可以更简单防止假溢出的发生，但队列大小是固定的。
• 在循环队列中，当队列为空时，有 front=rear，而当所有队列空间全占满时，也有 front=rear 。
• 为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是 front=rear ，而队列判满的条件是 front=（rear+1)%MaxSize 。

图 2.1

2.1 类的初始化

• 建立一个类作为循环队列；
• 类里面建立一个数组，用于存储队列中的元素；
• 建立两个变量，一个存储当前的队首坐标，一个存储当前的队尾坐标；
• 建立一个变量，用于存储队列的长度；

图 2.2

2.2 构造函数的建立

• 建立一个有参的构造函数，参数为最大能存储元素的个数；
• 因为循环队列有一个位置是作为辅助位置不存储元素，故循环队列的长度需设置为最大存储元素的个数 + 1；
• 将数组的长度传至存储长度的变量中；（ 可以写为 数组名.length 也可以直接写 最大存储元素的个数 + 1 ）

图 2.3

2.3 添加元素方法的编写

• 循环队列有两种插入元素的方法，一种是在队首插入，一种是在队尾插入；
• 两个方法都是需要先判断队列是否为满，如果未满直接返回 false 代表插入失败；
• 在确定可以插入元素的时候，队首插入方法是先将元素插入当前位置再将队首位置向前移动一位，因为计算机不知道我们所建立的是一个循环队列，所以我们需要判断队首坐标是否是位于最小的坐标，如果位于最小坐标的话将当前坐标赋予元素之后需要将坐标移动到最大坐标的位置；
• 队尾的插入方法跟队首几乎一样，不同的是队尾需要先向后移动一位坐标再填入元素，同时队尾也需要进行判断是否为最大坐标，如果是最大坐标则需要将队尾位置移动到最小坐标的位置上；

判断为空，为满的方法介绍在本文 2.6

图 2.4

2.4 删除元素方法的编写

• 删除元素也有两种方法，一种是在队首删除，一种是在队尾删除，事实上循环队列不用真正意义上的删除元素，只要对队首队尾坐标位置的移动限制能获取的元素就相当于进行了删除操作；
• 删除方法首先要判断队列是否为空，如果为空则代表无法删除元素，则直接返回 false ；
• 跟插入不同的是队首坐标要进行的是后移操作，队尾要进行的是前移操作，移动方法跟插入是一模一样的；

图 2.5

2.5 获取队首队尾元素方法的编写

• 在进行获取操作的时候首先要判断队列是否为空，如果为空则没有元素可以取出则直接返回 -1 ；
• 需要注意的是队首位置是不存储元素的所以需要返回的是队首后一个位置的元素（队首坐标位置最大坐标时，返回的是最小坐标上的元素），而队尾元素可以直接返回；

图 2.6

2.6 判断为空和为满的方法编写

• 循环队列判断为空的方法就是判断队首坐标是否跟队尾坐标处于同一个位置，如果处于同一个位置则表示当前队列为空；
• 循环队列判断为满的方法就是判断队尾坐标的下一个坐标是否是队首坐标的位置，如果是则表示队列为满；

图 2.6

三、代码分享及力扣评分

3.1 力扣评分

• 执行用时稳定在 4 ms ，内存消耗在 41.7 ~ 43 MB 之间徘徊；

图 3.1

3.2 代码分享

class MyCircularDeque {
    private int[] element;
    private int head = 0;
    private int last = 0;
    private int Max;

    public MyCircularDeque(int k) {
        element = new int[k + 1];
        Max = element.length;
    }

    public boolean insertFront(int value) {
        if( isFull() ){
            return false;
        }else{
            element[head] = value;
            if ( head == 0 ){
                head = Max - 1;
            }else {
                head--;
            }
            return true;
        }
    }

    public boolean insertLast(int value) {
        if( isFull() ){
            return false;
        }else{
            if ( last == Max - 1 ){
                last = 0;
            }else {
                last++;
            }
            element[last] = value;
            return true;
        }
    }

    public boolean deleteFront() {
        if( isEmpty() ){
            return false;
        }else{
            if ( head == Max - 1 ){
                head = 0;
            }else {
                head++;
            }
            return true;
        }
    }

    public boolean deleteLast() {
        if( isEmpty() ){
            return false;
        }else{
            if ( last == 0 ){
                last = Max - 1;
            }else {
                last--;
            }
            return true;
        }
    }

    public int getFront() {
        if( isEmpty() ){
            return -1;
        }else{
            int temp;
            if ( head == Max - 1 ){
                temp = 0;
            }else {
                temp = head + 1;
            }
            return element[temp];
        }
    }

    public int getRear() {
        if( isEmpty() ){
            return -1;
        }else{
            return element[last];
        }
    }

    public boolean isEmpty() {
        if ( head == last ){
            return true;
        }else {
            return false;
        }
    }

    public boolean isFull() {
        if ( (last + 1) % Max == head ){
            return true;
        }else {
            return false;
        }
    }
}
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