Question

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.

Difficulty:Medium

Category:

Analyze

Solution

class MyCircularDeque {
 public:
  MyCircularDeque(int n) : buffer(n, -1), cnt(0), k(n), front(n - 1), rear(0){ }

  bool insertFront(int value) {
    if (cnt == k) return false;
    buffer[front--] = value;
    front = (front + k) % k;
    ++cnt;
    return true;
  }

  bool insertLast(int value) {
    if (cnt == k) return false;
    buffer[rear++] = value;
    rear %= k;
    ++cnt;
    return true;
  }

  bool deleteFront() {
    if (cnt == 0) return false;
    front = (front + 1) % k;
    --cnt;
    return true;
  }

  bool deleteLast() {
    if (cnt == 0) return false;
    rear = (rear - 1 + k) % k;
    --cnt;
    return true;
  }

  int getFront() { return cnt == 0 ? -1 : buffer[(front + 1) % k]; }
  int getRear() { return cnt == 0 ? -1 : buffer[(rear - 1 + k) % k]; }
  bool isEmpty() { return cnt == 0; }
  bool isFull() { return cnt == k; }

 private:
  vector<int> buffer;
  int cnt;
  int k;
  int front;
  int rear;
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""