一、简要认识队列
结构：一种特殊的线性表
入队：在队尾插入一个元素
出队：在队头删除一个元素
特点：先入先出
空队列：队中没有元素
二、队列的封装
class Queue {
items = {
}
count = 0
lowCount = 0
dequeue() {
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] = data
this.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();
