LeetCode 641：Design Circular Deque
LeetCodeの「DesignCircularDeque」のソリューションを投稿しています。レビューをご希望の場合は、ご確認ください。ありがとうございました！
問題
循環両端キュー（deque）の実装を設計します。
実装は次の操作をサポートする必要があります。
MyCircularDeque(k)：コンストラクター、両端キューのサイズをkに設定します。insertFront()：Dequeの前にアイテムを追加します。操作が成功した場合はtrueを返します。insertLast()：Dequeの後ろにアイテムを追加します。操作が成功した場合はtrueを返します。deleteFront()：Dequeの前面からアイテムを削除します。操作が成功した場合はtrueを返します。deleteLast()：Dequeの背面からアイテムを削除します。操作が成功した場合はtrueを返します。getFront()：Dequeからフロントアイテムを取得します。dequeが空の場合は、-1を返します。getRear()：Dequeから最後のアイテムを取得します。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、1000]の範囲になります。
- 操作回数は[1、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;
};
回答
dequeの内容とサイズ/インデックス（
k, count, head, tail）に同じタイプを使用すると、気分が悪くなります。少なくとも、kそしてそうあるcountべきですstd::vector::size_type。あなたが両端キューをバックアップしているので
std::vector、作るheadとルックスは、より慣用的。tailstd::vector::iteratork最もわかりやすい名前ではありません。考えてみてくださいcapacity。これが
std::vector固定サイズの両端キューをバックアップするのに最適なコンテナかどうかはわかりません。結局のところ、ポイントはstd::vector動的なサイズを持つことです。std::array、または単純な古いCスタイルの配列でさえ、より自然に見えます。
要素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異なる10進値の？データ型ごとに15個のクラスを作成することはできません。
したがって、C ++でテンプレートを使用して、ジェネリック を作成できるようにしますdeque。
構文は単純です
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
これで、新しい両端キューを作成するときに、を実行できますdeque<any_data_type> my_deque。
使用する場所はどこでもValueType、に置き換えますT。
C ++が行うことはany_data_type、コンパイル時Tにそのデータ型を取得して置き換えることです。これをプログラムに実装すると、テンプレートがC ++でどのように機能するかについて多くのことを学び、将来のプロジェクトで役立ちます。
C ++のテンプレート
これはあなたのコードのテーマだと思いますconst。あなたがそれを置いたところでは、何の利益もありません。そしてそれがそこにあるべきであるということは他の場所から欠けています。これらの戻り値はスカラーであるため、それらをマークしても文字通り効果がないためMyCircularDeque、すべての関数inはconst前にドロップする必要constがあります。insertLast(const int value)少し効果がありますが、実際には重要ではありません。
置くために最も重要な場所は、constののconstネス変更することでthis、あなたのためにgetとis方法を。括弧の後にconst追加する必要があります。これは、メソッドがメンバーを変更しないという約束を登録します。