Neunomizuの日記

俺だけが俺だけじゃない

# 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を使います.

先頭と末尾を指す変数headtailを使います.

また,現在のqueueの要素数を表すsizeと最初に決めたqueueの容量maxSizeをコンストラクタで定義します.

このようにすると以下のように定義出来ます()

計算量

  • 時間計算量
    • コンストラクタを実行する時は$O(k)$
    • 他は全て$O(1)$
  • 空間計算量
    • コンストラクタを実行する時は$O(k)$
    • 他は全て$O(1)$

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();
 */
 ```