欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

641. Design Circular Deque

程序员文章站 2022-04-04 08:30:44
...

1,题目要求
Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.
641. Design Circular Deque
实现一个双向循环队列。

2,题目思路
很麻烦,首先,STL中是有双向队列deque的,但是如果直接用肯定是不行的了,因此需要定义额外的容器来实现这个循环的双向队列。
因此,对于这道题,定义了一个vector,来作为存储这个循环双向队列的容器。其次,对于循环队列,在添加元素时所用的则是mod,来进行循环的实现。
另外,循环队列的实现,有两种方式,一种是k个元素,而另外一种则是额外开辟新的空间,即k+1个空间存储k个元素,这个额外的空间作为队列为空还是为满的一个判断条件。

3,程序源码

class MyCircularDeque {
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k) {
        array.resize(k+1, 0);
        size = k + 1;
        front = 0, back = 1;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if(isFull())
            return false;
        array[front] = value;
        front = (front + size -1) % size;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if(isFull())
            return false;
        array[back] = value;
        back = (back + 1) % size;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if(isEmpty())
            return false;
        front = (front + 1) % size;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if(isEmpty())
            return false;
        back = (back + size - 1) % size;
        return true;
    }

    /** Get the front item from the deque. */
    int getFront() {
        if(isEmpty())
            return -1;
        return array[(front + 1) % size];
    }

    /** Get the last item from the deque. */
    int getRear() {
        if(isEmpty())
            return -1;
        return array[(back + size -1) % size];
    }

    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return (front+1)%size == back;
    }

    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return front == back;
    }
private:
    vector<int> array;
    int front, back;
    int size;
};