一、题目描述

设计实现双端队列。
你的实现需要支持以下操作:

  • MyCircularDeque(k):构造函数,双端队列的大小为k。
  • insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true。
  • insertLast():将一个元素添加到双端队列尾部。如果操作成功返回 true。
  • deleteFront():从双端队列头部删除一个元素。 如果操作成功返回 true。
  • deleteLast():从双端队列尾部删除一个元素。如果操作成功返回 true。
  • getFront():从双端队列头部获得一个元素。如果双端队列为空,返回 -1。
  • getRear():获得双端队列的最后一个元素。 如果双端队列为空,返回 -1。
  • isEmpty():检查双端队列是否为空。
  • isFull():检查双端队列是否满了。

二、题目解析

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class MyCircularDeque {

    // capacity 表示数组的容量,它的大小为 k + 1
    private int capacity ;

    // front 表示队头的位置
    private int front;

    // rear 表示队列尾部的下一个位置
    private int rear;

    // 这里使用数组来设计循环双端队列
    private int[] arr;


    public MyCircularDeque(int k) {

        // 需要空出一个额外的空间
        // 当队列中的元素有 k 个时,代表队列已满
        capacity = k + 1;

        // 这里使用数组来设计循环双端队列,数组的容量为 capacity
        // 即在数组中会空出一个额外的空间来不存储任何元素
        // 因为这样才能合理的区分出【队列为空】和【队列已满】这两种情况
        arr = new int[capacity];

        // 初始化队头指针
        front = 0;

        // 初始化队尾指针
        rear = 0;
    }

    // 在双端队列的队头添加元素 value
    public boolean insertFront(int value) {
        // 首先判断队列是否已满,没有其它的剩余空间
        // 如果队列已满,那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // front 向前移动
        // 由于 front 会移动到数组的最前面,如果再向前移动会出界
        // 那么这个时候就需要将 front 挪到数组结尾的位置
        // 可以通过取余运算来实现循环移动的这个操作
        front = ( front - 1  + capacity) % capacity;

        // 添加元素 value 到 front 这个位置
        arr[front] = value;

        // 添加元素成功,返回 true
        return true;

    }

    // 在双端队列的队尾添加元素 value
    public boolean insertLast(int value) {

        // 首先判断队列是否已满,没有其它的剩余空间
        // 如果队列已满,那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // 添加元素 value 到 rear 这个位置
        arr[rear] = value;

        // rear 向后移动
        // 由于 rear 会移动到数组的最尾部,如果再向后移动会出界
        // 那么这个时候就需要将 rear 挪到数组开头的位置
        // 可以通过取余运算来实现循环移动的这个操作
        rear = ( rear + 1 ) % capacity;

        // 添加元素成功,返回 true
        return true;

    }

    // 删除双端队列的队头元素
    public boolean deleteFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删,返回 false
            return false;
        }

        // 队头指针向后移动
        front = ( front + 1 ) % capacity;

        // 删除元素成功,返回 true
        return true;

    }

    // 删除双端队列的队尾元素
    public boolean deleteLast() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删,返回 false
            return false;
        }

        // 队尾指针向前移动
        rear = ( rear - 1 + capacity ) % capacity;

        // 删除元素成功,返回 true
        return true;
    }

    public int getFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选,根据题目要求返回 -1
            return -1;
        }

        // 否则返回 front 指向的元素就行
        return arr[front];

    }

    public int getRear() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选,根据题目要求返回 -1
            return -1;
        }

        // 否则返回 rear 位置的前一个元素就行
        return arr[(rear - 1 + capacity) % capacity];
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        // front 和 rear 指向同一个位置时,队列为空
        return front == rear;
    }

    public boolean isFull() {
        // 当队尾指针向后移动一个位置后,指向了队头时,那么说明队列已满
        return ( rear + 1 ) % capacity == front;
    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注