前端算法面试题1--栈、队列、链表、字典与哈希表
栈–后进先出
数据结构：数组
使用方法：pop（出栈） push（入栈）
算法题：有效的扣号
function isValid(s) {let stack = [];let map = {"(": ")","{": "}","[": "]"};for (let i = 0; i < s.length; i++) {let ch = s[i];// 如果是左括号，则入栈if (map[ch]) {stack.push(ch);} else {// 如果是右括号，检查栈顶的左括号是否与之匹配if (ch !== map[stack.pop()]) {return false;}}}// 最后检查栈是否为空，如果为空说明所有的括号都匹配，否则说明有不匹配的括号return stack.length === 0;
}console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true
队列-先进先出
数据结构：数组
使用方法：shift（出栈） push（入栈）
重点：js的任务队列
算法题：用两个栈实现队列。
队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构。以下是一个 JavaScript 队列问题的例子：用两个栈实现队列。
问题描述：
使用两个栈实现一个队列。提供两个方法：push，用于添加元素到队列，pop，用于从队列中删除元素。假设所有的操作都是有效的（比如，对一个空的队列不会调用 pop 操作）。
var Queue = function() {this.stack1 = [];this.stack2 = [];
};Queue.prototype.push = function(x) {this.stack1.push(x);
};Queue.prototype.pop = function() {if (this.stack2.length === 0) {while (this.stack1.length > 0) {this.stack2.push(this.stack1.pop());}}return this.stack2.pop();
};var queue = new Queue();
queue.push(1);
queue.push(2);
console.log(queue.pop()); // 1
queue.push(3);
console.log(queue.pop()); // 2
console.log(queue.pop()); // 3这个解决方案中，我们使用两个栈：stack1 和 stack2。当添加元素到队列时，我们只需要将元素压入 stack1。当从队列中删除元素时，我们将所有 stack1 中的元素依次弹出并压入 stack2，然后弹出 stack2 的栈顶元素。这样，就实现了队列的先进先出特性。如果 stack2 中还有元素，我们就直接弹出，而不需要再次将 stack1 中的元素转移过来。这是因为 stack2 中的元素都是比 stack1 中的元素更早添加到队列中的，所以应该优先出队。
链表
什么是链表
1.多个元素存储的列表
2.链表中的元素在内存中不是顺序存储的，而是通过“next”指针联系在一起的
链表和数组的区别
1、数组是有序存储的,在中间某个位置删除或者添加某个元素，其他元素要跟着动
2、链表中的元素在内存中不是顺序存储的，而是通过“next”
指针联系在一起的
区别一：
数组：下标
链表：next指针联系在一起
区别二：数据插入
数组：中间插入新的元素、其他元素需要重新计算
链表：不会重新计算，赋值/替换的感觉
区别三：查找
数组：通过下标进行查找即可
链表：每次查找都需要从头开始找
单向链表：
双向链表：
数据结构
let a={key:'a'}
let b={key:'b'}
let c={key:'c'}
let d={key:'d'}
a.next=b
b.next=c
c.next=d
d.next=null
console.log(a)
{"key": "a","next": {"key": "b","next": {"key": "c","next": {"key": "d","next": null}}}
}
//遍历链表
let obj=a;
while(obj&&obj.key){console.log(obj.key);obj=obj.next
}
//链表中插入元素
let m={key:'m'}
c.next=m;
m.next=d;
console.log(a)
//删除操作
c.next=d
console.log(a)
js中的原型链原理就是链表结构 通过__proto__连接
function fun(){}
console.log(new fun().__proto__)
instanceof的原理
JavaScript 中的 instanceof 运算符用于检测构造函数的 prototype 属性是否出现在某个实例对象的原型链上。
其原理可以概括为以下步骤：
获取对象的原型（proto 属性）。
对比该原型与构造函数的 prototype 属性。
如果相等，则返回 true。
如果不相等，则继续向上（proto.proto）追溯原型链并进行比较，直到原型链的终点 null。
如果在原型链上都没有找到与构造函数 prototype 属性相等的原型，则返回 false。
以下是一个简单的示例：
function MyConstructor() {}let instance = new MyConstructor();console.log(instance instanceof MyConstructor); // 输出：true在这个例子中，instance 是 MyConstructor 的一个实例，所以 instance instanceof MyConstructor 返回 true。
基于 instanceof 的原理，我们也可以手动实现一个 instanceof 的功能：
function myInstanceOf(instance, constructor) {let proto = Object.getPrototypeOf(instance);while (proto) {if (proto === constructor.prototype) {return true;}proto = Object.getPrototypeOf(proto);}return false;
}console.log(myInstanceOf([1,2,3],Array));
// 输出：true
环形链表
环形链表是一种特殊的链表，其中最后一个元素指向链表的某个位置，形成一个环。
问题：给定一个链表，确定链表中是否有环。
为了解决这个问题，我们可以使用“快慢指针”或者“龟兔赛跑”的算法。这个算法的原理是创建两个指针，一个快指针和一个慢指针。快指针每次移动两个节点，慢指针每次移动一个节点。如果链表中存在环，那么快指针和慢指针最终会在环中的某个位置相遇。
以下是使用JavaScript实现的代码：
function ListNode(val) {this.val = val;this.next = null;
}function hasCycle(head) {if (head === null || head.next === null) {return false;}let slow = head;let fast = head.next;while (slow !== fast) {if (fast === null || fast.next === null) {return false;}slow = slow.next;fast = fast.next.next;}return true;
}// 创建一个有环的链表
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // 创建环console.log(hasCycle(node1)); // 输出：true字典和哈希表
字典
字典：键值对存储的，类似于js的对象（键[key]都是字符串类型或者会转换成字符串类型）
字典==》map来表示，map的键不会转换类型（键[key]可以伊任何形式存在）
哈希表 又叫==>散列表
在js中没有哈希表，哈希表是字典的一种实现
记住这句就行 下面可以不用看了 避免混乱
哈希表与字典的区别：
区别一：如果找key对应的value需要遍历key，那么想省略这个步骤可以使用哈希表表示
区别二：排列顺序
字典是根据添加的顺序进行排列的，哈希表不是添加顺序进行排列的
哈希表（Hash Table），也被称为散列表或哈希映射，是一种便于查找和存储数据的数据结构。它的特点是通过一种称为哈希函数（Hash Function）的计算方法，将存储的数据与表中的一个位置（或者说索引）关联起来，从而实现高效的数据查找。
下面是一种通俗的解释：
想象你拥有一个巨大的仓库，需要在其中存储各种各样的物品。一个直接的方法就是，把每一件物品都放入一个巨大的箱子中，然后每次需要某个物品时，都从箱子的一头开始找，直到找到需要的物品。但是，这种方法效率低下，尤其当你需要找的物品在箱子的另一头时。
于是，你想出了一个新的方法：为每一个物品都分配一个特定的编号，然后按照编号的顺序将物品放置在仓库的特定位置。这样，下次需要某个物品时，你只需要查看这个物品的编号，就可以直接找到物品所在的位置，大大提高了查找的效率。
哈希表就是这样一个"仓库"，它使用哈希函数为每一份数据生成一个"编号"（我们称之为哈希值），然后将数据存储在相应的位置。当你需要查找数据时，只需要输入数据或者关键字，哈希函数会告诉你数据在哪里，从而实现快速查找。
然而，哈希表并非完美无缺。有时，不同的数据经过哈希函数计算可能会得到相同的哈希值，这种情况我们称之为哈希碰撞。为了解决这个问题，哈希表有多种解决碰撞的方法，如开放定址法、链地址法等。
在 JavaScript 中，没有专门的哈希表（Hash Table）这个数据类型。但是，JavaScript 提供了一些可以实现哈希表功能的对象和数据结构，例如对象（Object）、Map 对象以及 Set 对象。
JavaScript 对象：JavaScript 的对象（Object）可以被看作是键值对的集合，或者说字符串到值的映射。因此，它们可以用来实现哈希表的功能。但是，JavaScript 对象的键必须是字符串或者 Symbol，不能是其他类型的值。
<JAVASCRIPT>
let obj = {};
obj["key1"] = "value1";
obj["key2"] = "value2";
console.log(obj[“key1”]); // 输出：“value1”
Map 对象：ES6 引入了 Map 类型，它类似于普通的 Object，但 Map 的键可以是任何类型的值。Map 提供了一些有用的方法，如 set(key, value)、get(key)、has(key)、delete(key) 和 size 等。
<JAVASCRIPT>
let map = new Map();
map.set("key1", "value1");
map.set("key2", "value2");console.log(map.get("key1")); // 输出："value1"
Set 对象：Set 是 ES6 引入的新的数据结构，类似于数组，但 Set 的成员是唯一且无序的，没有重复的值。
以上这些数据结构都可以实现哈希表的功能，如存储键值对、检查键是否存在、删除键等。但实际上，这些数据结构的内部实现可能并不完全基于哈希算法，它们可能使用了其他的数据结构和算法优化性能。