# LeetCode Medium 622. Design Circular Queue
tags: leetcode
こういう実装系の問題をやっていきたいのでやっている系です.
次にHash系とTrieを実装したら,多分普通の問題を解きます.
問題
アイデア
Circular Queueとは要するにFIFOで,最後の部分が先頭に繋がっているようなデータ構造です.
利点としては,普通のqueueでは空間が余ってしまいますが,このデータ構造では空間を有効的に活用できるという点です.
MyCircularQueue(k)
: Constructor.queueの大きさをk
に定める.Front
: queueの先頭を手に入れる.空なら-1
を返す.Rear
: queueの末尾を手に入れる.空なら-1
を返す.enQueue(value)
: circular queueに要素を挿入する.操作が成功したかをbool値で返す.deQueue()
: circular queueから要素を削除する.操作が成功したかをbool値で返す.isEmpty()
: queueが空か返す.isFull()
: queueが満杯か返す.
解法
queueとしてstd::vector
を使います.
先頭と末尾を指す変数head
とtail
を使います.
また,現在のqueueの要素数を表すsize
と最初に決めたqueueの容量maxSize
をコンストラクタで定義します.
このようにすると以下のように定義出来ます()
計算量
C++
class MyCircularQueue { public: /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k): queue(vector<int>(k)), head(0), tail(-1), size(0), maxSize(k) {} /** Insert an element into the circular queue. Return true if the operation is successful. */ bool enQueue(int value) { if (isFull()) return false; tail = (tail + 1) % maxSize; queue[tail] = value; ++size; return true; } /** Delete an element from the circular queue. Return true if the operation is successful. */ bool deQueue() { if (isEmpty()) return false; head = (head + 1) % maxSize; --size; return true; } /** Get the front item from the queue. */ int Front() { if (isEmpty()) return -1; else return queue.at(head); } /** Get the last item from the queue. */ int Rear() { if (isEmpty()) return -1; else return queue.at(tail); } /** Checks whether the circular queue is empty or not. */ bool isEmpty() { return size == 0; } /** Checks whether the circular queue is full or not. */ bool isFull() { return size == maxSize; } private: vector<int> queue; int head; int tail; int size; const int maxSize; }; /** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue* obj = new MyCircularQueue(k); * bool param_1 = obj->enQueue(value); * bool param_2 = obj->deQueue(); * int param_3 = obj->Front(); * int param_4 = obj->Rear(); * bool param_5 = obj->isEmpty(); * bool param_6 = obj->isFull(); */ ```