• LeetCode 每日一题——641. 设计循环双端队列

    1.题目描述

    641. 设计循环双端队列

    设计实现双端队列。

    实现 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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    2.解题思路与代码

    2.1 解题思路

    非常基础的数据结构题目，手写双端队列。手写队列的难点就在于需要头尾插入和删除，这个时候很多人会想到使用 head 和 rear 两个变量指向头和尾来进行操作，但是由于是循环队列，所以在计算队列长度和插入删除判断的时候会很麻烦。因此需要换个思路，使用 head 指向头，不用 rear 指向尾，而使用 size 记录队列当前元素个数，在需要尾部插入和尾部删除的时候通过 head 和 size 计算出队尾的位置。这样的话能够让代码更简洁，并且计算也很简单。因此，我们只需要四个变量便能够完成题目，分别是存饭元素的数组 arr、队列最大长度 max （可以用数组长度代替）、队列的头 head、队列当前元素个数 size。接下来就是对题目要求实现的方法进行

    • 构造方法 MyCircularDeque(int k)

      使用构造方法对参数进行初始化。初始化数组并且数组长度为 k，队列最大长度 max 设置为 k，队头 head 指向 0 位置，队列元素个数 size 也初始化为 0。

      public MyCircularDeque(int k) {
  arr = new int[k];
  head = 0;
  size = 0;
  max = k;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    • 头部插入 insertFront

      从头部插入首先需要判断队列是否已经满了，如果满了的话直接返回 -1 不能插入。如果没满的话我们需要让head迁移一位，并且在位置上插入元素。在 head 前移的时候需要判断 head 是否在 0 位置，如果在 0 位置则将 head 移动到数组最后一位，即 max-1。

      public boolean insertFront(int value) {
  if (size == max) {
    return false;
  }
  head = head - 1 == -1 ? max - 1 : head - 1;
  arr[head] = value;
  size++;
  return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9

    • 尾部插入 insertLast

      与队头插入相同，先判断队列是否已满，如果满了直接返回 -1。在队尾插入时，我们需要使用 head 和 size 来计算队尾的位置 head+size-1 便是当前队列队尾元素的位置，由于需要插入一个元素因此在 head+size 位置放入新元素即可。此时需要注意越界问题，如果 head+size 大于等于数组长度 max，即超过了数组最后一位，则需要回到 0 位置继续计算，即在 (head + size) % max 位置插入新元素。在队头和队尾插入元素之后，size 大小增加 1。

      public boolean insertLast(int value) {
  if (size == max) {
    return false;
  }
  int rear = head + size >= max ? (head + size) % max : head + size;
  arr[rear] = value;
  size++;
  return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9

    • 删除头部 deleteFront

      删除元素首先判断队列长度是否为 0 ，如果为 0 则返回 false 无法删除。删除队头元素，那么我们需要把 head 往后移动一位即可，移动的时候同样需要判断 head 是否越界，如果 head 超出数组，则回到 0 位置。

      public boolean deleteFront() {
  if (size == 0) {
    return false;
  }
  head = head + 1 == max ? 0 : head + 1;
  size--;
  return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8

    • 删除尾部 deleteLast

      与删除队头一样，删除元素首先判断队列长度是否为 0 ，如果为 0 则返回 false 无法删除。因为队尾是通过 head 和 size 计算得到的，所以直接使用 size 减一就可以了。

      public boolean deleteLast() {
  if (size == 0) {
    return false;
  }
  size--;
  return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    • 获取头部 getFront

      首先判断队列是否为空，如果为空返回 -1，否则返回 head 位置元素。

      public int getFront() {
  if (size == 0) {
    return -1;
  }
  return arr[head];
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    • 获取尾部 getRear

      首先判断队列是否为空，如果为空返回 -1，否则计算队尾位置，返回 head+size-1 位置元素。同样的 head+size-1 如果超过数组，则回到 0 位置从头开始。

      public int getRear() {
  if (size == 0) {
    return -1;
  }
  int rear = head + size - 1 >= max ? (head + size - 1) % max : head + size - 1;
  return arr[rear];
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    • 队列是否为空 isEmpty 和队列是否已满 isFull

      由于我们使用 size 记录队列长度，因此队列是否为空和队列是否已满就非常方便了，直接返回 size 是否等于 0 和 size 是否等于数组长度即可。

      public boolean isEmpty() {
  return size == 0;
}

public boolean isFull() {
  return size == max;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    2.2 代码

    class MyCircularDeque {

    int[] arr;
    int head;
    int size;
    int max;

    public MyCircularDeque(int k) {
        arr = new int[k];
        head = 0;
        size = 0;
        max = k;
    }

    public boolean insertFront(int value) {
        if (size == max) {
            return false;
        }
        head = head-1==-1?max-1:head-1;
        arr[head] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (size == max) {
            return false;
        }
        int rear = head + size >= max ? (head + size) % max : head + size;
        arr[rear] = value;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (size == 0) {
            return false;
        }
        head = head + 1 == max ? 0 : head + 1;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (size == 0) {
            return false;
        }
        size--;
        return true;
    }

    public int getFront() {
        if (size == 0) {
            return -1;
        }
        return arr[head];
    }

    public int getRear() {
        if (size == 0) {
            return -1;
        }
        int rear = head + size - 1 >= max ? (head + size - 1) % max : head + size - 1;
        return arr[rear];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == max;
    }
}

    • 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

    2.3 测试结果

    通过测试

    测试结果

    3.总结

    • 使用 size 记录队列长度，队尾通过 head+size-1 来计算求得
    • 在添加和删除元素时需要注意越界问题
  • 相关阅读:
    创建Asp.net MVC项目实现视图页面数据传值显示
    苹果平板可以用别的电容笔吗？电容笔和Apple pencil区别
    【C++】《C++ Primer》第六章 知识点总结
    华为S5700交换机初始化和配置telnet，ssh用户方法
    服务器优化
    突破神奇的Cloudflare防火墙
    Day08--自定义组件的插槽
    Java并发面试题：（七）ThreadLocal原理和内存泄漏
    大厂FPGA的面试题
    做外贸必知——你还不知道外贸拼箱技巧吗
  • 原文地址：https://blog.csdn.net/qq_38550836/article/details/126345734