# 622. Design Circular Queue
Difficulty: Medium

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-09-12
**/
#include <cstdlib>
#include <iostream>
using namespace std;

#define USE_MSVC 1

#define LINK_LIST_VER 1
#define ARRAY_VER 0

#if USE_MSVC
#include <crtdbg.h>
#endif

#if LINK_LIST_VER

struct Node {
  int value{0};
  Node *next{nullptr};
};

class MyCircularQueue {
 public:
  /** Initialize your data structure here. Set the size of the queue to be k. */
  explicit MyCircularQueue(int k) {
    queue_size_ = k;

    queue_buffer_ = new Node;
    front_ = queue_buffer_;
    rear_ = front_;

    while (--k > 0) {
      queue_buffer_->next = new Node;
      queue_buffer_ = queue_buffer_->next;
    }

    if (queue_buffer_ != nullptr) {
      queue_buffer_->next = front_;
    }
  }

  ~MyCircularQueue() {
    while (queue_size_-- > 0) {
      auto *p = queue_buffer_;
      queue_buffer_ = queue_buffer_->next;
      delete p;
    }
  }

  /** Insert an element into the circular queue. Return true if the operation is
   * successful. */
  bool enQueue(int value) {
    if (isFull()) {
      return false;
    }

    if (!isEmpty()) {
      rear_ = rear_->next;
    }
    is_empty_ = false;
    rear_->value = value;

    return true;
  }

  /** Delete an element from the circular queue. Return true if the operation is
   * successful. */
  bool deQueue() {
    if (isEmpty()) {
      return false;
    }

    if (front_ == rear_) {
      is_empty_ = true;
    } else {
      front_ = front_->next;
    }

    return true;
  }

  /** Get the front item from the queue. */
  int Front() {
    if (isEmpty()) {
      return -1;
    }

    return front_->value;
  }

  /** Get the last item from the queue. */
  int Rear() {
    if (isEmpty()) {
      return -1;
    }

    return rear_->value;
  }

  /** Checks whether the circular queue is empty or not. */
  bool isEmpty() { return is_empty_ && (front_ == rear_); }

  /** Checks whether the circular queue is full or not. */
  bool isFull() { return rear_->next == front_; }

 private:
  bool is_empty_{true};
  int queue_size_{0};
  Node *queue_buffer_{nullptr};
  Node *front_{nullptr};
  Node *rear_{nullptr};
};

#elif ARRAY_VER

class MyCircularQueue {
public:
	/** Initialize your data structure here. Set the size of the queue to be k. */
	explicit MyCircularQueue(int k) {
		buffer_ = new int[k];
		buffer_size_ = k;
	}

	~MyCircularQueue() {
		delete [] buffer_;
	}

	/** Insert an element into the circular queue. Return true if the operation is successful. */
	bool enQueue(int value) {
		if (isFull()) {
			return false;
		}

		rear_index_ = (!is_empty_) ? (rear_index_ + 1) % buffer_size_ : rear_index_;
		buffer_[rear_index_] = value;
		is_empty_ = false;
		return true;
	}

	/** Delete an element from the circular queue. Return true if the operation is successful. */
	bool deQueue() {
		if (is_empty_) {
			return false;
		}

		if (front_index_ == rear_index_) {
			is_empty_ = true;
			return true;
		}

		front_index_ = (front_index_ + 1) % buffer_size_;
		return true;
	}

	/** Get the front item from the queue. */
	int Front() {
		return (!is_empty_) ? buffer_[front_index_] : -1;
	}

	/** Get the last item from the queue. */
	int Rear() {
		return (!is_empty_) ? buffer_[rear_index_] : -1;
	}

	/** Checks whether the circular queue is empty or not. */
	bool isEmpty() {
		return is_empty_;
	}

	/** Checks whether the circular queue is full or not. */
	bool isFull() {
		return (((rear_index_ + 1) % buffer_size_) == front_index_);
	}

private:
	bool is_empty_{ true };
	int *buffer_{ nullptr };
	int front_index_{ 0 };
	int rear_index_{ 0 };
	int buffer_size_{ 0 };
};

#endif

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

int main(int argc, char *argv[]) {
  const int k = 3;
  const int value_1 = 1;
  const int value_2 = 2;
  const int value_3 = 3;
  const int value_4 = 4;

  int ret_int = 0;
  bool ret_bool = false;

  MyCircularQueue *obj = new MyCircularQueue(k);
  ret_bool = obj->enQueue(value_1);  // true
  ret_bool = obj->enQueue(value_2);  // true
  ret_int = obj->Front();            // 1
  ret_int = obj->Rear();             // 2
  ret_bool = obj->isEmpty();         // false
  ret_bool = obj->isFull();          // false

  ret_bool = obj->enQueue(value_3);  // true
  ret_int = obj->Front();            // 1
  ret_int = obj->Rear();             // 3
  ret_bool = obj->isEmpty();         // false
  ret_bool = obj->isFull();          // true

  ret_bool = obj->enQueue(value_4);  // false
  ret_int = obj->Front();            // 1
  ret_int = obj->Rear();             // 3
  ret_bool = obj->isEmpty();         // false
  ret_bool = obj->isFull();          // true

  ret_bool = obj->deQueue();  // true
  ret_int = obj->Front();     // 2
  ret_int = obj->Rear();      // 3
  ret_bool = obj->isEmpty();  // false
  ret_bool = obj->isFull();   // false

  ret_bool = obj->enQueue(value_4);  // true
  ret_int = obj->Front();            // 2
  ret_int = obj->Rear();             // 4
  ret_bool = obj->isEmpty();         // false
  ret_bool = obj->isFull();          // true

  ret_bool = obj->deQueue();  // true
  ret_int = obj->Front();     // 3
  ret_int = obj->Rear();      // 4
  ret_bool = obj->isEmpty();  // false
  ret_bool = obj->isFull();   // false

  ret_bool = obj->deQueue();  // true
  ret_int = obj->Front();     // 4
  ret_int = obj->Rear();      // 4
  ret_bool = obj->isEmpty();  // false
  ret_bool = obj->isFull();   // false

  ret_bool = obj->deQueue();  // true
  ret_int = obj->Front();     // -1
  ret_int = obj->Rear();      // -1
  ret_bool = obj->isEmpty();  // true
  ret_bool = obj->isFull();   // false

  delete obj;

#if USE_MSVC
  _CrtDumpMemoryLeaks();
#endif
  return EXIT_SUCCESS;
}

## Result

Success
Details
Runtime: 52 ms, faster than 63.03% of C++ online submissions for Design Circular Queue.
Memory Usage: 17.1 MB, less than 5.16% of C++ online submissions for Design Circular Queue.

###### tags: `LeetCode-Medium` `C++`