Topic describes

Design your loop queue implementation. A circular queue is a linear data structure that operates on a FIFO (first-in, first-out) basis and the tail of the queue is connected behind the head of the queue to form a loop. It is also known as a “ring buffer”.

One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.

Your implementation should support the following:

MyCircularQueue(k): constructor that sets the queue length to K. Front: Retrieves elements from the team leader. If the queue is empty, -1 is returned. Rear: Gets the last element of the team. If the queue is empty, -1 is returned. EnQueue (value): Inserts an element into the loop queue. Return true on successful insertion. DeQueue (): Removes an element from the loop queue. Return true if deleted successfully. IsEmpty (): checks if the loop queue isEmpty. IsFull (): checks if the loop queue isFull.

Analysis of the

Input: k as the maximum length of the queue Output: an instance has the queue method required by the problem

Their thinking

As JS does not have such a data structure, we can use an array to store data. Then we can use two Pointers to point to the head and tail of the queue. When adding or deleting elements, we can change the pointer.

For a data structure, the most important thing is its attributes. So for this circular queue, we definitely need a queue property to store the array, where all our data is stored.

I also need a property that represents the current length of the queue, and I’ll set it to count, the capacity of the queue.

We don’t need to store two indexes to represent the head and tail, we actually need to store one headIndex, the tail index can be calculated:

tailIndex = (headIndex + count - 1) % capacity
Copy the code

Rather, move headIndex a few places to the right until you reach tail, and then, if you’re at the end of the queue, move the remaining steps back from the beginning.

Maintaining too many variables is more likely to cause bugs, so we just need to calculate them when we use them.

My advice is to start by writing down the method for determining “full” and “empty”, because it will be used elsewhere:

/ * * *@return {boolean}* /
MyCircularQueue.prototype.isEmpty = function () {
  return !this.count;
};

/ * * *@return {boolean}* /
MyCircularQueue.prototype.isFull = function () {
  return this.count === this.capacity;
};
Copy the code

If count and capacity are equal, you can determine whether they are full. Check if count is 0 to see if it is an empty queue.

Then look at the addition:

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) return false;

  this.queue[(this.headIndex + this.count) % this.capacity] = value;
  this.count++;
  return true;
};
Copy the code

For adding an element to the queue,

First check if it is full, if so return false.

The next step is to find the tailIndex by calculation

And then finally set value, return true in the index array and we’re adding elements.

For deletion:

/ * * *@return {boolean}* /
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) return false;

  this.queue[this.headIndex] = undefined;
  this.count--;
  this.headIndex = (this.headIndex + 1) % this.capacity;
  return true;
};
Copy the code

The first step is to determine whether it is null

And then we make headIndex undefined, which is deleting the element

Reduce count, the current length of the queue

Let’s move headIndex back one bit, because we want to take into account that headIndex has reached the end of the array, so let headIndex + 1 modulo the capacity

The last return true

For the end of the change, do not repeat

code

/ * * *@param {number} k* /
var MyCircularQueue = function (k) {
  this.queue = [];
  this.headIndex = 0;
  this.count = 0;
  this.capacity = k;
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) return false;

  this.queue[(this.headIndex + this.count) % this.capacity] = value;
  this.count++;
  return true;
};

/ * * *@return {boolean}* /
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) return false;

  this.queue[this.headIndex] = undefined;
  this.count--;
  this.headIndex = (this.headIndex + 1) % this.capacity;
  return true;
};

/ * * *@return {number}* /
MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) return -1;

  return this.queue[this.headIndex];
};

/ * * *@return {number}* /
MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) return -1;

  return this.queue[(this.headIndex + this.count - 1) % this.capacity];
};

/ * * *@return {boolean}* /
MyCircularQueue.prototype.isEmpty = function () {
  return !this.count;
};

/ * * *@return {boolean}* /
MyCircularQueue.prototype.isFull = function () {
  return this.count === this.capacity;
};

/** * Your MyCircularQueue object will be instantiated and called as such: * var obj = new MyCircularQueue(k) * var param_1 = obj.enQueue(value) * var param_2 = obj.deQueue() * var param_3 = obj.Front() * var param_4 = obj.Rear() * var param_5 = obj.isEmpty() * var param_6 = obj.isFull() */
Copy the code

The complexity of the

Time: O(1), all operations are constant level complexity space: O(N), need to store all data in arrays