LeetCode 641:设计圆形设计

Question

我正在为LeetCode的“设计循环设计”发布一个解决方案。如果你想复习，请这样做。谢谢!

问题

设计循环双结束队列(deque)的实现。

您的实现应该支持以下操作：

• MyCircularDeque(k)：构造函数，将deque的大小设置为k。
• insertFront()：在Deque前面添加一个项目。如果操作成功，则返回true。
• insertLast()：在Deque的后面添加一个项目。如果操作成功，则返回true。
• deleteFront()：从Deque前面删除一个项目。如果操作成功，则返回true。
• deleteLast()：从Deque的后面删除一个项目。如果操作成功，则返回true。
• getFront()：从Deque获得最前面的项目。如果设备是空的，返回-1。
• getRear()：从Deque获得最后一项。如果设备是空的，返回-1。
• isEmpty()：检查Deque是否为空。
• isFull()：检查Deque是否已满。

示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);            // return true
circularDeque.insertLast(2);            // return true
circularDeque.insertFront(3);           // return true
circularDeque.insertFront(4);           // return false, the queue is full
circularDeque.getRear();            // return 2
circularDeque.isFull();             // return true
circularDeque.deleteLast();         // return true
circularDeque.insertFront(4);           // return true
circularDeque.getFront();           // return 4

注：

• 所有的值都在0,000的范围内。
• 操作的数量将在1000的范围内。
• 请不要使用内置的Deque图书馆。

代码：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

struct MyCircularDeque {
        MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}

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

            stream[head] = value;
            --head;
            head += k;
            head %= k;
            ++counts;

            return true;
        }

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

            stream[tail] = value;
            ++tail;
            tail %= k;
            ++counts;

            return true;
        }

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

            ++head;
            head %= k;
            --counts;

            return true;
        }

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

            --tail;
            tail += k;
            tail %= k;
            --counts;

            return true;
        }

        const int getFront() {
            return isEmpty() ? -1 : stream[(head + 1) % k];
        }

        const int getRear() {
            return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
        }

        const bool isEmpty() {
            return !counts;
        }

        const bool isFull() {
            return counts == k;
        }

    private:
        using ValueType = std::uint_fast16_t;
        std::vector<ValueType> stream;
        ValueType counts;
        ValueType k;
        ValueType head;
        ValueType tail;
}; 

Answer 1

• 使用相同类型的deque内容和大小/索引(k, count, head, tail)感觉是错误的。至少，k和count应该是std::vector::size_type。
• 由于您正在使用std::vector备份deque，所以head和tail std::vector::iterator看起来更像惯用用法。
• k不是最具描述性的名称。考虑一下capacity。
• 我不确定std::vector是否是备份固定尺寸设备的最佳容器。毕竟，std::vector的重点是要有一个动态大小。std::array，甚至是一个普通的C风格数组，看起来更自然。

Answer 2

我认为这是您的代码的一个主题：const，您已经放置它的地方，没有任何好处；它在其他地方也没有它应该存在的地方。MyCircularDeque中的每个函数都应该将const放在前面，因为这些返回值是标量的，因此标记它们const实际上没有任何效果。insertLast(const int value)有更多的效果，但实际上并不重要。

放置const最重要的地方是为get和is方法修改this的一致性。他们需要在括号后添加const。这将注册一个承诺，即这些方法不会修改任何成员。

Answer 3

您可以在构造函数中调用stream.reserve(k)来提高向量的效率，因为您知道只有k元素，所以.reserve()会预先分配内存。

更喜欢使用std::size_t结束int

int k将是std::size_t k

您还没有声明一个复制构造函数或复制赋值算子。如果您希望将一个Deque分配给另一个，这可能会导致问题。

内衬您的struct的一些成员函数，如isEmpty()、getRear()、getFront()可以提高容器的性能，但它将是空间的交换。

如果您这样做只是为了完成挑战，则可以忽略下一部分

。

模板

现在，您的deque必须使用std::uint_fast16_t。但如果我想用名字做deque呢？还是一个不同十进制值的deque？我不能只为每种数据类型创建15个类。

因此，我将在模板中使用C++，以便创建一个通用 deque。

语法很简单

template < typename T >
struct deque
{
    public:
        // public member functions
    private:
        std::vector< T > stream;
};

现在，当您想要创建一个新的deque时，您可以执行deque<any_data_type> my_deque。

无论您在哪里使用ValueType，都可以用T替换它。

C++所做的就是在编译时使用any_data_type并用该数据类型替换T。在您的程序中实现这一点将教会您很多关于模板如何在C++中工作的知识，这将对您的未来项目有所帮助。

C++中的模板