栈
JS 实现栈
- 栈 : 用数组实现
- 入栈 push ---- 时间复杂度 O(1)
- 出栈 pop ---- 时间复杂度 O(1)
let stack = []; // 入栈 stack.push("a"); stack.push("b"); console.log(stack); // 出栈 -- 先进后出 -- b 出栈 stack.pop(); console.log(stack);
队列
先进先出
JS 实现队列（方案1）
- 队列 : 用数组实现
- 入队 push ---- 时间复杂度 O(1)
- 出队 shift ---- 时间复杂度 O(n)
let queue = []; // 入队 queue.push("a"); queue.push("b"); console.log(queue); // 出队 -- 先进先出 -- a 出队 queue.shift(); console.log(queue);
JS 实现队列（方案2）
- 队列 : 用数组实现
- 入队 unshift ---- 时间复杂度 O(n)
- 出队 pop ---- 时间复杂度 O(1)
let queue = []; // 入队 queue.unshift("a"); queue.unshift("b"); console.log(queue); // 出队 -- 先进先出 -- a 出队 queue.pop(); console.log(queue);
【推荐】JS 链表实现队列（方案3）
时间复杂度 O(1)
// 实现队列的：入队、出队、长度 // PS：要用链表来实现，用数组性能较低 class MyQueue { constructor() { this.length = 0; // 长度 this.head = null; this.tail = null; } // 从 tail 入队 add(value) { const newNode = { value }; if (this.length === 0) { // 长度是 0 this.head = newNode; this.tail = newNode; } else { // 长度 > 0 ，把 newNode 拼接到 tail 位置 this.tail.next = newNode; this.tail = newNode; } this.length++; // 累加长度 } // 从 head 出队 delete() { if (this.length <= 0) return null; let value = null; if (this.length === 1) { // 长度是 1 ，只有一个元素了 value = this.head.value; // 先找到结果 // 重置 head tail this.head = null; this.tail = null; } else { // 长度 > 1 ，多个元素 value = this.head.value; // 先找到结果 this.head = this.head.next; // 重置 head } // 减少长度，返回结果 this.length--; return value; } } // 功能测试 const queue = new MyQueue(); queue.add(100); console.log("length1", queue.length); // 1 queue.add(200); console.log("length2", queue.length); // 2 console.log("delete1", queue.delete()); // 100 queue.add(300); console.log("length3", queue.length); // 2 console.log("delete2", queue.delete()); // 200 console.log("length4", queue.length); // 1 console.log("delete3", queue.delete()); // 300 console.log("length5", queue.length); // 0 console.log("delete4", queue.delete()); // null
