1. Title Description

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,Set the queue length to k 。
  • Front: Get elements from team leader. If the queue is empty, -1 is returned.
  • Rear: Gets the last element of the queue. 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 whether the loop queue is empty.
  • isFull(): Checks whether the loop queue is full.

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

Tip:

  • All values are in the range 0 to 1000;
  • Operands will be in the range 1 to 1000;
  • Do not use the built-in queue library.

Analysis:

  • Create an array of size K to store data

  • Definition variable: Capacity Indicates the maximum queue capacity

  • Front indicates the index of the team leader

  • Rear indicates the index at the end of the queue

  • Count indicates the current queue length

  • The initial value of capacity is K

  • The front initial value is 0

  • Rear is initialized to 0

  • Count is initialized to 0, and count==0 means the list is empty

  • When adding elements toqueue[rear]Insert the element at the position, and then move the tail index backrear = (rear + 1)%capacityAnd,count++

  • When you delete an element,frontJust move it backwards,front=(front)%capacityAnd,count--

  • When you add an element,rear = (rear+1) % capacityAnd,count++

  • Repeat the preceding steps

  • Rear index forcapacity-1.rear = (rear + 1)%capacityEquals zero, and then you have a cycle

  • Continue adding elements to perform the above operation whencapacityandcountIf they are equal, the queue is full.

juejin.cn/post/702891…

Two, code implementation

/** * @param {number} k */ var MyCircularQueue = function(k) {this.queue = new Array(k+1) this.front = 0 This. Rear = 0 this. Max = k}; /** * @param {number} value * @return {boolean} */ MyCircularQueue.prototype.enQueue = function(value) { if(this.isFull()) return false this.queue[this.rear] = value this.rear = (this.rear+1) % (this.max+1) return true }; /** * @return {boolean} */ MyCircularQueue.prototype.deQueue = function() { if(this.isEmpty()) return false this.front =  (this.front + 1) % (this.max+1) return true }; /** * @return {number} */ MyCircularQueue.prototype.Front = function() { if(this.isEmpty()) return -1; return this.queue[this.front] }; /** * @return {number} */ MyCircularQueue.prototype.Rear = function() { if(this.isEmpty()) return -1; return this.queue[(this.rear + this.max) % (this.max + 1)] }; /** * @return {boolean} */ MyCircularQueue.prototype.isEmpty = function() { return ((this.rear - this.front + this.max +  1) % (this.max+1)) == 0 }; /** * @return {boolean} */ MyCircularQueue.prototype.isFull = function() { return ((this.rear - this.front + this.max + 1) % (this.max+1)) == this.max };Copy the code