每日一题:设计循环双端队列(LeetCode 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 。

解答

class MyCircularDeque {
public:
    vector<int> arr;
    //指向当前队首元素的位置
    int front;
    //指向当前队尾元素的下一个位置,即下一个入队元素的位置
    int rear;
    //表示数组的容量,大小为k+1
    int cap;

    MyCircularDeque(int k) {
        cap = k + 1;
        arr = vector<int>(cap);
        front = 0;
        rear = 0;
    }

    bool insertFront(int value) {
        if(isFull())
        {
            return false;
        }

        front = (front - 1 + cap) % cap;
        arr[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if(isFull())
        {
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1) % cap;
        return true;
    }

    bool deleteFront() {
        if(isEmpty())
        {
            return false;
        }

        front = (front + 1) % cap;
        return true;
    }

    bool deleteLast() {
        if(isEmpty())
        {
            return false;
        }

        rear = (rear -1 + cap)%cap;

        return true;
    }

    int getFront() {
        if(isEmpty())
        {
            return -1;
        }

        return arr[front];
    }

    int getRear() {
        if(isEmpty())
        {
            return -1;
        }
        return arr[(rear-1+cap)%cap];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1)% cap == front;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */
扫描关注程序区
THE END
分享
二维码
打赏
海报
每日一题:设计循环双端队列(LeetCode 641)
题目 设计实现双端队列。 实现 MyCircularDeque 类: - MyCircularDeque(int k) :构造函数,双端队列最大为 k 。 - boolean insertFront():将一个元素添加到双……
<<上一篇
下一篇>>