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

Title 1

622. Design a loop queue

There is a linked list in ascending order, and you are given the head node of the linked list. Please delete all the nodes in the linked list that have duplicate numbers, and only keep the original list that does not have duplicate numbers.

Returns a linked list of results, also in ascending order.

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:

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 4

 

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.

Ask questions

  • How does the queue loop?

Analysis of the

  • Start by creating an array of size K to store the 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.

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