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. ,

Example:

circularQueue.enQueue(1); Circularqueue.enqueue (2); Circularqueue.enqueue (3); Circularqueue.enqueue (4); // Return false, the queue is full circularqueue.rear (); Circularqueue.isfull (); Circularqueue.dequeue (); Circularqueue.enqueue (4); // Return true circularqueue.rear (); / / return 4Copy the code

Source: LeetCode link: leetcode-cn.com/problems/de… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

  • Requirements: Length limited, fifO.
  • Set the array to be used for storage. The length of the array cannot exceed the parameter limit.
  • Based on the first-in, first-out principle, elements are added to the end of the array to ensure that the advanced element precedes the last one.
  • Delete element Deletes the first element of an array.
  • If length is 0, the array is empty. If length is k, the array is full. If length is 0, the first array is the head of the queue, and the last array is the opposite end.

code

@param {number} k */ var MyCircularQueue = function(k) {this.leng=k; let list=[]; // Private attributes, no external access required}; /** * insert element, No vacancy, returns false * @ param value * @ return {Boolean} {number} * / MyCircularQueue prototype. The enQueue = function (value) { If (list.length<this.leng){list.push(value); if(list.length<this.leng){list.push(value); return true; } return false; }; /** * delete element, Delete returns true on success * @ return. {Boolean} * / MyCircularQueue prototype. DeQueue = function () {if (list) length > 0) { List.splice (0,1); return true; } return false; }; / * * * * @ return return to the team the first elements. {number} * / MyCircularQueue prototype. Front = function () {if (list) length > 0) {return list [0]. } return -1; }; / * * * * @ return return of the elements. {number} * / MyCircularQueue prototype. Rear = function () {if (list) length > 0) {return list.slice(-1); } return -1; }; / * * * check whether the circular queue is empty * @ return. {Boolean} * / MyCircularQueue prototype. IsEmpty = function () {if (list. Length < = 0) {return true;  } return false; }; / * * * check whether the circular queue is the full * @ return. {Boolean} * / MyCircularQueue prototype. IsFull = function () {if (list. The length > = this. Leng) { return true; } return false; }; /** * 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