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

一、简要认识队列

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

二、队列的封装

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();