Topic describes

Design a loop queue that supports the following operations

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

The code analysis

The constructor

List = new Array(x)

Head Is used to store the head element of the queue (it can be used to handle pointing when exiting the queue)

Tail Is used to store the last element of the queue (processed when appending elements, processed when reading the top element, read the last element of the queue)

Count is used to store the total number of elements (this can be used to determine if an element is full, or to compare if an element is empty)

Max Is used to store the maximum length of queues

var MyCircularQueue = function (k) {
  this.list = new Array(k);
  this.head = 0; / / the head pointer
  this.tail = 0; / / the tail pointer
  this.count = 0; // Number of elements
  this.max = k;
};
Copy the code

Checks whether the queue is empty

Null means the number of elements is 0

MyCircularQueue.prototype.isEmpty = function () {
  return this.count === 0;
};
Copy the code

Check whether the queue isFull isFull

Max === count

MyCircularQueue.prototype.isFull = function () {
  return this.count === this.max;
};

Copy the code

Get element Front from team head

If it is empty, -1 is returned

MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) return -1;
  return this.list[this.head]; // Return the top element
};

Copy the code

Return the Rear element of the queue

If tail is 0, the element at the end of the queue is the end of the list. In other cases, the element at the end of the queue is tail-1

You can also use formulas

(this.tail – 1 + this.max) % this.max

MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) return -1;
  // if (tail === 0) {
  // tail = this.max - 1;
  // } else {
  // tail -= 1;
  / /}

  return this.list[(this.tail - 1 + this.max) % this.max];
};
Copy the code

The team the enQueue

Return false if the queue is full

When joining the queue, the corresponding value of the tail pointer is value

count + 1

The trailing pointer moves back, and the loop starts at 0 to the last bit value

Returns true

MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) return false;
  this.list[this.tail] = value;
  this.count += 1; // There is one more element
  this.tail = (this.tail + 1) % this.max; // The tail pointer is updated
  return true;
};

Copy the code

Out of the team to deQUeue

Return false if the queue is empty

The head pointer is set to null and the head pointer is the next element. When the head pointer is the last element, start from the beginning

A simple formula for the same idea

(this.head + 1)%this.max

And count minus one

And return true

MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) return false;
  this.list[this.head] = null;
  this.head = (this.head + 1) % this.max;
  this.count -= 1;
  return true;
};

Copy the code

The above is the analysis of the idea of designing the circular queue. The implementation method is linear structure. The space complexity is slightly higher, but the time complexity and understanding difficulty are very friendly, which is very helpful for us to master the data structure of the queue