LeetCode 641: Design Circular Deque

Question

I'm posting a solution for LeetCode's "Design Circular Deque". If you'd like to review, please do so. Thank you!

Problem

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.

Example:

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

Note:

• All values will be in the range of [0, 1000].
• The number of operations will be in the range of [1, 1000].
• Please do not use the built-in Deque library.

Code:

// 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

• Using the same type for the deque contents and the sizes/indices (k, count, head, tail) feels wrong. At least, k and count should be std::vector::size_type.

• Since you are backing up the deque with std::vector, making head and tail the std::vector::iterator looks more idiomatic.

• k is not the most descriptive name. Consider capacity.

• I am not sure that std::vector is the best container to back up the fixed size deque. After all, the point of std::vector is to have a dynamic size. std::array, or even a plain old C-style array, looks more natural.

• vnp: @Emma I wish there was one.

Answer 2

I think this is a theme for your code: const, where you've put it, has no benefit; and it's missing from other places that it should be there. Every single function in MyCircularDeque should drop the const out front, because those return values are scalar so marking them const has literally no effect. insertLast(const int value) has slightly more effect but is really not important.

The most important place to put const is to modify the const-ness of this for your get and is methods. They need to have const added after the parentheses. This registers a promise that the methods do not modify any members.

• user228914: declaring a parameter const does have an effect. It makes sure that you will never modify the value. All in all, it is a good practice to declare variables that you will not modify const or constexpr if the value can be calculated at compile-time. Use of const in function parameters

Answer 3

You can call stream.reserve(k) in the constructor to improve the efficiency of the vector because you know that you will only have k elements, so .reserve() will pre-allocate the memory.

Prefer using std::size_t over int
int k would be std::size_t k

You haven't declared a copy constructor nor a copy assignment operator. This can cause issues if you wanted to assign one Deque to another.

Inlining some member functions of your struct like isEmpty(), getRear(), getFront() can improve the performance of your container, but it will be a trade for space.

If you are doing this for the sole purpose of completing the challenge, you can ignore the next part

Templates

Right now, your deque is bound to use std::uint_fast16_t. But what if I wanted to make a deque of names? Or a deque of different decimal values? I can't just create 15 classes for each of the data types.

Hence, I will use templates in C++ so I can create a generic deque.

The syntax is simple

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

Now when you want to create a new deque, you can do deque<any_data_type> my_deque.

Wherever you would use ValueType, you replace it with T.

What C++ does is that it takes any_data_type and replaces T with that data type during compile-time. Implementing this in your program will teach you a lot about how templates work in C++ which will be helpful in your future projects.

Templates in C++

• user228914: @Emma not really, I haven't been into competitive programming a lot, although i do like to solve some problems from time to time. Thanks for the feedback :)