【js版数据结构学习之队列】

一、简要认识队列

结构：一种特殊的线性表
入队：在队尾插入一个元素
出队：在队头删除一个元素
特点：先入先出
空队列：队中没有元素

二、队列的封装

class Queue {items = {}count = 0lowCount = 0dequeue() {if(this.isEmpty()){return undefined}let res = this.items[this.lowCount]delete this.items[this.lowCount]this.lowCount++return res}enqueue(data) {this.items[this.count] = datathis.count++}front() {return this.items[this.lowCount]}isEmpty() {return this.size() === 0}size() {return this.count-this.lowCount}clear() {this.items = {}this.count = 0;this.lowCount = 0}toString() {let str = ""for(let i =this.lowCount;i<this.count;i++){str += `${this.items[i]} `}return str}
}

三、队列的应用

1.栈和队列的转换

class MyStack {constructor() {this.queue1 = [];this.queue2 = [];}push(x) {// 将元素加入非空队列if (this.queue1.length === 0) {this.queue2.push(x);} else {this.queue1.push(x);}}pop() {if (this.empty()) {throw new Error("Stack is empty!");}// 将非空队列中的元素转移到辅助队列中，直到剩余一个元素const nonEmptyQueue = this.queue1.length === 0 ? this.queue2 : this.queue1;const emptyQueue = this.queue1.length === 0 ? this.queue1 : this.queue2;while (nonEmptyQueue.length > 1) {emptyQueue.push(nonEmptyQueue.shift());}// 取出最后一个元素并返回return nonEmptyQueue.shift();}top() {if (this.empty()) {throw new Error("Stack is empty!");}// 将非空队列中的元素转移到辅助队列中，直到剩余一个元素const nonEmptyQueue = this.queue1.length === 0 ? this.queue2 : this.queue1;const emptyQueue = this.queue1.length === 0 ? this.queue1 : this.queue2;while (nonEmptyQueue.length > 1) {emptyQueue.push(nonEmptyQueue.shift());}// 取出最后一个元素并返回const top = nonEmptyQueue.shift();emptyQueue.push(top);return top;}empty() {return this.queue1.length === 0 && this.queue2.length === 0;}
}

2.全排列

function permute(nums) {const result = [];const queue = [[]]; // 初始队列中只有一个空数组while (queue.length > 0) {const current = queue.shift(); // 取出队列中的当前排列// 如果当前排列的长度等于原始数组的长度，说明找到了一种排列方式if (current.length === nums.length) {result.push(current);continue;}// 尝试将原始数组中剩余的数字加入到当前排列中for (let i = 0; i < nums.length; i++) {// 如果当前数字已经在排列中，跳过这个数字if (current.includes(nums[i])) {continue;}queue.push([...current, nums[i]]); // 将当前数字加入到排列中并加入队列}}return result;
}

3.任务调度

使用队列来管理需要异步执行的任务，确保它们按照顺序执行。

// 定义一个任务队列
const taskQueue = [];// 添加任务到队列
function enqueueTask(task) {taskQueue.push(task);
}// 执行队列中的任务
function processTasks() {while (taskQueue.length > 0) {const task = taskQueue.shift(); // 从队列头部取出任务task(); // 执行任务}
}// 示例任务
function task1() {console.log('Task 1');
}function task2() {console.log('Task 2');
}function task3() {console.log('Task 3');
}// 添加任务到队列
enqueueTask(task1);
enqueueTask(task2);
enqueueTask(task3);// 执行任务队列
processTasks();

4.缓存管理

使用队列来管理数据的加载和展示，避免同时加载大量数据。

// 定义一个数据缓存队列
const dataQueue = [];// 添加数据到队列
function enqueueData(data) {dataQueue.push(data);
}// 展示队列中的数据
function showData() {while (dataQueue.length > 0) {const data = dataQueue.shift(); // 从队列头部取出数据console.log('Data:', data);}
}// 添加数据到队列
enqueueData('Data 1');
enqueueData('Data 2');
enqueueData('Data 3');// 展示数据队列
showData();