“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

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.

Source: LeetCode leetcode-cn.com/problems/de…

Their thinking

  1. The core of the topic is the reuse of space. We can use the JS array to realize the circular queue, by adding elements to the end of the push method to achieve the queue, by removing the first element in the array by shift method to achieve the queue, itself is the reuse of space.
  2. Circular queue method has been given, as long as one implementation can be:
  • MyCircularQueue(k): Initializes array and queue capacity in the constructor.
  • Front: Returns -1 if isEmpty() is true, otherwise returns the 0th element of the array.
  • Rear: Return -1 if isEmpty() is true, otherwise return arr[arr.length-1].
  • EnQueue (value): Return false if isFull() is true, otherwise add elements to the end by push.
  • DeQueue (): Return false if isEmpty() is true, otherwise remove the first element of the array with shift.
  • IsEmpty (): the queue isEmpty when the array length is 0.
  • IsFull (): the queue isFull when the array length is the maximum.

Code implementation

/** * @param {number} k */ var MyCircularQueue = function(k) { Shift = new Array() this.queue = new Array() this.capacity = k}; /** * @param {number} value * @return {boolean} */ MyCircularQueue.prototype.enQueue = function(value) { if (this.isFull()) return false // Queue this.queue.push(value) return true}; / * * * @ return {Boolean} * / MyCircularQueue prototype. DeQueue = function () {if (this. IsEmpty ()) return false / / first remove elements from the queue  this.queue.shift() return true }; / * * * @ return {number} * / MyCircularQueue prototype. Front = function () {if (this. IsEmpty ()) return 1 / / return returns the first element  this.queue[0] }; / * * * @ return {number} * / MyCircularQueue prototype. Rear = function () {if (this. IsEmpty ()) return 1 / / return returns the tail element this.queue[this.queue.length - 1] }; / * * * @ return {Boolean} * / MyCircularQueue prototype. IsEmpty = function () {/ / when the queue length of 0 is empty queue return this. The queue. The length = = = 0 }; / * * * @ return {Boolean} * / MyCircularQueue prototype. IsFull = function () {/ / if the queue length is equal to the capacity is the queue is full return this. The queue. The length === this.capacity };Copy the code

If there are mistakes welcome to point out, welcome to discuss together!