Queue definition
A queue is an ordered item that follows a first-in, first-out rule. A very vivid example is the queue for dry rice, the first to come first service, then the queue at the end.
Calm analysis
The functions of queues include the following:
- Add new elements to the end of the queue
- Remove the first item in the queue
- Returns the first element in the queue
- Whether the queue contains elements
- Length of queue
Code implementation
class Queue {
constructor() {
this.index = 0;
this.outIndex = 0; // The index of the first queue item
this.items = {};
}
add(ele) {
this.items[this.index] = ele
this.index++
}
remove() {
if (this.isEmpty()) {
return undefined
}
const delEle = this.items[this.outIndex]
delete this.items[this.outIndex]
this.outIndex++
}
size() {
return this.index - this.outIndex
}
isEmpty() {
return this.size()
}
clear(){
this.index = 0;
this.outIndex = 0;
this.items = {}; }}Copy the code
Double – endian queue (Deque) definition
A special queue that allows us to add or remove elements from the front and back of the queue, following the principle of fifO and FIFO, is a combination of stack and queue data structure.
Calm analysis
The functions of a dual-ended queue include the following:
- Adds a new element to the front of a two-ended queue
- Adds a new element to the back-end of the two-ended queue
- Remove the first item in a two-end queue
- Remove the first item at the back end of a two-end queue
- Returns the first element at the beginning and end of a two-ended queue
- Whether a double-ended queue contains elements
- The length of a two-endian queue
Code implementation
class Deque {
constructor() {
this.count = 0
this.outIndex = 0 // The front end index value
this.items = {}
}
addFront(ele) {
/** there are three ways to add elements to the front end of a double-ended queue: * 1- The front end queue is empty, so adding elements to the front end is the same as adding elements to the front end * 2- If the front end element is deleted,outIndex will be ++, so the front end needs to outIndex before adding elements to the front end - * 3- If the front end queue has elements */
if (this.isEmpty()) {
this.addBack(ele)
} else if (this.outIndex > 0) {
this.outIndex--
this.items[this.outIndex] = ele
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1]}this.count++
this.outIndex = 0
this.items[this.outIndex] = ele
}
}
addBack(ele) {
this.items[this.count] = ele
this.count++;
}
removeFront() {
if (this.isEmpty()) {
return undefined
}
const delEle = this.items[this.outIndex]
delete this.items[this.outIndex]
this.outIndex++
}
removeBack() {
if (this.isEmpty()) {
return undefined
}
this.count--
const delEle = this.items[this.count]
delete this.items[this.count]
return delEle
}
peekFront() {
if (this.isEmpty()) {
return undefined
}
return this.items[0]}peekBack() {
if (this.isEmpty()) {
return undefined
}
return this.items[Object.keys(this.items).length - 1]}size() {
return this.count
}
isEmpty() {
return this.size() == 0}}Copy the code