JavaScript data structure (2) queue

A queue is a first-in, first-out data structure

There are no queues in JavaScript, but you can use Array for all the functions of queues

Common queue operations: push, Shift, queue[0]

1. Queue definition

First in, first out (queuing)

Queues add new elements at the tail and remove elements from the top

The most recently added element must be at the end of the queue

USES:

Line up for lunch in the canteen

Task queue in JS asynchrony

Count the number of recent requests

…

2. Perform queue operations

create

class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};  // Use objects for storage}}Copy the code

methods

Enqueue (Element (s)) : Adds one (or more) new items to the end of the queue

enqueue(element(s)) {
    this.items[this.count] = element;
    this.count++;
}
Copy the code

Dequeue () : removes the first item in the queue and returns the removed element

dequeue() {
    if(this.isEmpty()) {
        return undefined;
    }
    const result = this.items[this.lowestCount];
	delete this.items[this.lowestCount];
	this.lowestCount++;
    return result;
}
Copy the code

Peek () : Returns the first element in the queue and will be the first element removed (no element removed, only element information is returned)

peek() {
    if(this.isEmpty()) {
        return undefined;
    }
    return this.items[this.lowestCount];
}
Copy the code

IsEmpty () : Returns true if the queue contains no elements, false otherwise

isEmpty() {
    return this.count - this.lowestCount === 0;
    //return this.size() === 0;
}
Copy the code

Size () : Returns the number of elements contained in the queue, similar to the length property of an array
```
size() {
    return this.count - this.lowestCount;
}
Copy the code
```

Clear (): Clears all elements

clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
}
Copy the code

The toString () :

toString() {
    if (this.isEmpty()) {
        return ' ';
    }
    let objString = `The ${this.items[this.lowestCount]}`;  // Template string
    for (let i = this.lowestCount + 1; i < this.count; i++){
        objString = `${objString}.The ${this.items[i]}`;
    }
    return objString;
}
Copy the code

Since the first index in Queue is not set to 0, the Queue is iterated from lowestCount

3. The queue class USES

With the stack

4. Dual-end queue definition

Fifo + LIFO + FIFO

A special queue that can add and remove elements both before and after

Application:

Cancel the operation

5. Perform operations on dual-end queues

create

class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {}; }}Copy the code

methods

Same as queue: isEmpty, clear, size, toString

Different from queue:

AddFront (Element) : Adds a new element to the front end

addFront(element) {
    if (this.isEmpty()) {  // If empty, add directly to the end of the queue
        this.addBack(element);
    } else if (this.lowestCount > 0) {  // There is an element removed from the front, put the new element in this position
        this.lowestCount--;
        this.items[this.lowestCount] = element;
    } else {
        for (let i = this.count; i > 0; i--) {
            this.items[i] = this.items[i - 1];  // Move back a bit
        }
        this.count++;
        this.lowestCount = 0;
        this.items[0] = element; }}Copy the code

AddBack (Element) : Adds a new element to the back end (same as enqueue())

addBack(element) {
    this.items[this.count] = element;
    this.count++;
}
Copy the code

RemoveFront () : Removes the first element from the front (same as dequeue)

removeFront() {
    if(this.isEmpty()) {
        return undefined;
    }
    const result = this.items[this.lowestCount];
	delete this.items[this.lowestCount];
	this.lowestCount++;
    return result;
}
Copy the code

RemoveBack () : Removes the first element from the back end (same as pop in the Stack class)
```
removeBack() {
	return this.items.pop();
}
Copy the code
```

PeekFront () : Returns the first element of the front end (same as peek)

peekFront() {
	return this.items[this.items.length - 1];
}
Copy the code

PeekBack () : Returns the first element on the back end (same as the peek method in the Stack class)
```
peekBack() {
	return this.items[this.items.length - 1];
}
Copy the code
```

6. Use the Deque class

Same as above

7. Solve problems

Circular queue

function hotPotato(elementsList, num) {
	const queue = new Queue();
	const elimitatedList = [];
	for (let i = 0; i < elementsList.length; i++) {
		queue.enqueue(elementsList[i]);
	}
	while (queue.size() > 1) {
		for (let i = 0; i < num; i++) {
			queue.enqueue(queue.dequeue());
		}
		elimitatedList.push(queue.dequeue());
	}
	return {
		eliminated: elimitatedList,
		winner: queue.dequeue()
	};
}

const names = ['a'.'b'.'c'.'d'.'e'.'f'.'g'.'h'.'i'.'j'];
const result = hotPotato(names, 10);
result.eliminated.forEach(name= > {
	console.log(`${name}Get knocked out of the drum pass game. `);
});
console.log('The winner:${result.winner}`);
Copy the code

palindrome

function palindromeChecker(aString) {
    if (
        aString === undefined || 
        aString === null|| (aString ! = =null && aString.length === 0)) {return false;
    }
    const deque = new Deque();
    const lowerString = aString.toLocaleLowerCase();  // Convert to lowercase
    let isEqual = true;
    let firstChar, lastChar;
    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString.charAt(i)); // Add a new element to the back end
    }
    while (deque.size() > 1 && isEqual) {
        firstChar = deque.removeFront(); // Remove the first element from the front end
        lastChar = deque.removeBack(); // Remove the first element from the back end
        if(firstChar ! == lastChar) { isEqual =false; }}return isEqual;
}
Copy the code

An LeetCode

var RecentCounter = function() {
    this.q = [];
};

/ * * *@param {number} t
 * @return {number}* /
RecentCounter.prototype.ping = function(t) {
   this.q.push(t);
   while(this.q[0] < t - 3000) {this.q.shift(); // Delete anything beyond this range
   } 
   return this.q.length;
};

/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
Copy the code