622. Design loop queues

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: 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 1:

MyCircularQueue circularQueue = new MyCircularQueue(3); Circularqueue.enqueue (1); // Set the length to 3 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

Solution a primal

Circular queues are implemented using native arrays and methods, focusing only on functionality

The idea is to take advantage of the existing queue nature of the native array, which is easy to implement with push and shift, and then determine the length of the array. It’s not exactly what they say but it does all the things so let’s just do them.

Code implementation

/ * * *@param {number} k* /
var MyCircularQueue = function (k) {
  this.k = k // Queue length
  this.queue = [] / / the queue
}

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) {
    return false
  } else {
    this.queue.push(value)
    return true}}/ * * *@return {boolean}* /
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) {
    return false
  } else {
    this.queue.shift()
    return true}}/ * * *@return {number}* /
MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) {
    return -1
  }
  return this.queue[0]}/ * * *@return {number}* /
MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) {
    return -1
  }
  return this.queue[this.queue.length - 1]}/ * * *@return {boolean}* /
MyCircularQueue.prototype.isEmpty = function () {
  return this.queue.length === 0
}

/ * * *@return {boolean}* /
MyCircularQueue.prototype.isFull = function () {
  return this.queue.length === this.k
}
Copy the code

Solution two: simulation

In a queue of fixed length, add one element on entry, move the queue head back one bit on exit, and start storing again if false overflow occurs.

The property of a fixed-length circular queue uses previously free space, as shown in Figure 3. When the end of the queue is reached, there is still space in front of it to use for a circular effect.

  1. injsCan be used innew Array(k), the element isemptyLength ofkAn array of.
  2. The initial index for both the head and tail of the team is 0.
  3. When an element is added to a team, the element is added to the end of the team and then moved back one place.
  4. When an element comes out of a queue, move the head of the queue back one bit so that the element before the head is empty.
  5. The number of existing elements is recorded when joining and leaving the team, joining plus1And out of the team1. Used to determine if a queue is full (count = k) or the Empty Team (count = 0).
  6. False overflow problem resolved. Although the index will exceed the length of the queue, it can be usedTake more thanLet the index start all over again.

Code implementation

/ * * *@param {number} k* /
var MyCircularQueue = function (k) {
  this.k = k // Queue length
  this.queue = new Array(k) // Specifies the length of the queue
  this.head = 0 // first index
  this.tail = 0 // End index
  this.count = 0 // The number of elements in the team
}

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

  // Add an element to the end of the queue
  this.queue[this.tail] = value
  // Move the back of the line one place. (In order to start over when a false overflow occurs, the remainder operation can be looped.)
  this.tail = (this.tail + 1) % this.k
  // The number of elements in the queue increases by one
  this.count += 1

  return true
}

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

  // Let the leader of the team move back one.
  this.head = (this.head + 1) % this.k
  // The number of elements in the queue is reduced by one
  this.count -= 1

  return true
}

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

  return this.queue[this.head]
}

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

  // start index + number of elements - 1 = end index
  return this.queue[(this.head + this.count - 1) % this.k]
}

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

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

/ / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
// ========================== @test ==================================
/ / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
let circularQueue = new MyCircularQueue(3) // Set the length to 3
console.log(circularQueue.enQueue(1)) / / return true
console.log(circularQueue.enQueue(2)) / / return true
console.log(circularQueue.enQueue(3)) / / return true
console.log(circularQueue.enQueue(4)) // Return false, the queue is full
console.log(circularQueue.Rear()) / / return 3
console.log(circularQueue.isFull()) / / return true
console.log(circularQueue.deQueue()) / / return true
console.log(circularQueue.enQueue(4)) / / return true
console.log(circularQueue.Rear()) / / return 4
Copy the code

In this paper, to participate in

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign.