设计循环双端队列

力扣641题——设计循环双端队列

方法一：使用数组实现——略

方法二：使用双向链表实现——重点

需要实现以下方法：

• 初始化双端队列
• 插入元素到队列头
• 插入元素到队列尾
• 删除队列头元素
• 删除队列尾元素
• 得到队列头元素
• 得到队列尾元素
• 判断队列是否为空
• 判断队列是否满

class MyCircularDeque {

    public MyCircularDeque(int k) {
    }
    
    public boolean insertFront(int value) {
    }
    
    public boolean insertLast(int value) {
    }
    
    public boolean deleteFront() {
    }
    
    public boolean deleteLast() {
    }
    
    public int getFront() {
    }
    
    public int getRear() {
    }
    
    public boolean isEmpty() {
    }
    
    public boolean isFull() {
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */
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

首先解决数据结构问题：

1. 队列节点类——包括prev指针、next指针以及链表节点值val
2. 队列头尾节点——head、tail
3. 队列容量及队列当前大小—— capacity及size

    private class Node{
        Node prev;
        Node next;
        int val;
        Node(int val){
            this.val = val;
        }
    }

    private Node head;
    private Node tail;
    private int capacity;
    private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13

初始化双端队列——初始化capacity和size

    public MyCircularDeque(int k) {
        capacity = k;
        size = 0;
    }
1
2
3
4

向双端队列头尾插入元素

注意：

1. 队列是否为满 —— 为满则直接返回false
2. 队列是否为空 —— 为空则 head=tail
3. 插入结束更新size: size++

    public boolean insertFront(int value) {
        if(size == capacity){
            return false;
        }
        Node node = new Node(value);
        if(size == 0){
            tail = head = node;
        } else{
            head.prev = node;
            node.next = head;
            head = node;
        }
        size++;
        return true;
    }
    
    public boolean insertLast(int value) {
        if(size == capacity){
            return false;
        }
        Node node = new Node(value);
        if(size == 0){
            head = tail = node;
        } else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
        return true;
    }
    
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

删除双端队列头尾

注意：

1. 队列是否为空——为空直接返回false
2. 队列是否只含一个元素——影响指针移动
3. 删除后更新size——size–

  public boolean deleteFront() {
        if(size == 0){
            return false;
        }
        head = head.next;
        if(head != null){
            head.prev = null;
        }
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if(size == 0){
            return false;
        }
        tail = tail.prev;
        if(tail != null){
            tail.next = null;
        }
        size--;
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

得到首位元素

    public int getFront() {
        if(size == 0){
            return -1;
        }
        return head.val;
    }
    
    public int getRear() {
        if(size == 0){
            return -1;
        }
        return tail.val;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

判断队列是否为空为满

    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
1
2
3
4
5
6
7