LeetCode 641:设计圆形设计
我正在为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;
}; 回答 3
Code Review用户
发布于 2020-10-13 20:52:56
- 使用相同类型的deque内容和大小/索引(
k, count, head, tail)感觉是错误的。至少，k和count应该是std::vector::size_type。 - 由于您正在使用
std::vector备份deque，所以head和tailstd::vector::iterator看起来更像惯用用法。 k不是最具描述性的名称。考虑一下capacity。- 我不确定
std::vector是否是备份固定尺寸设备的最佳容器。毕竟，std::vector的重点是要有一个动态大小。std::array，甚至是一个普通的C风格数组，看起来更自然。
Code Review用户
发布于 2020-10-13 20:53:22
我认为这是您的代码的一个主题：const，您已经放置它的地方，没有任何好处；它在其他地方也没有它应该存在的地方。MyCircularDeque中的每个函数都应该将const放在前面，因为这些返回值是标量的，因此标记它们const实际上没有任何效果。insertLast(const int value)有更多的效果，但实际上并不重要。
放置const最重要的地方是为get和is方法修改this的一致性。他们需要在括号后添加const。这将注册一个承诺，即这些方法不会修改任何成员。
Code Review用户
发布于 2020-10-13 20:49:04
您可以在构造函数中调用stream.reserve(k)来提高向量的效率，因为您知道只有k元素，所以.reserve()会预先分配内存。
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++中工作的知识，这将对您的未来项目有所帮助。
https://codereview.stackexchange.com/questions/250609
复制相似问题
腾讯云开发者
