JS数据结构

数据结构的重要性。掌握常见的数据结构，可以利用一些数据结构去解决一些业务中的数据。

数据结构

栈(stack)

栈结构是一种受限的线性表。后进先出（LIFO：last in first out）。

栈常见的操作

• push：添加元素到栈顶 → 入栈
• pop：移除栈顶元素，同时返回被移除的元素 → 出栈
• peek：返回栈顶元素
• isEmpty：栈里是否有元素
• size：返回栈元素个数
• toString：栈结构以字符形式返回

实现一个栈结构，用栈结构来封装 十进制转二进制函数

function Stack(){
	this.arr = [];
	
	Stack.prototype.push = function (ele) {
		return this.arr.push(ele)
	}

	Stack.prototype.pop = function (){
		return this.arr.pop()
	}

	Stack.prototype.peek = function () {
		return this.arr?.[this.arr.length - 1]
	}

	Stack.prototype.isEmpty = function () {
		return this.arr?.length === 0
	}

	Stack.prototype.toString = function () {
		return this.arr.splice(',').join(' ')
	}
}

const s = new Stack()

有效括号

思路：

1. 采用栈结构，入栈出栈
2. 使用map映射

   function isValid(str) {
       let stack = [];
       let map = {
       '{': '}',
       '[': ']',
       '(': ')'
       }
   
       for(let i in str){
           let value = str[i]
           if(value === '{' || value === '[' || value === '('){
               stack.push(value)
           }else {
               let left = stack.pop(value)
               let right = map[left]
               if(value !== right){
                   return false
               }
           }
       }
   
       return stack?.length === 0
   }
   console.log(isValid("()"));      // true
   console.log(isValid("()[]{}"));  // true
   console.log(isValid("(]"));      // false
   console.log(isValid("([)]"));    // false
   console.log(isValid("{[]}"));    // true

队列(Queue)

队列结构也是一种受限的线性结构。先进先出（FIFO: first in first out）

队列常见的操作

• enqueue：向队列尾部添加一个元素 → 入队
• dequeue：移除队列的第一项，并返回被移除的元素 → 出队
• front：返回队列中第一个元素
• isEmpty：队列是否为空
• size：返回队列长度
• toString：将队列中的内容，转换为字符串

实现队列 - > 使用队列封装击鼓传花的方法

function Queue(){
	this.arr = []

	Queue.prototype.enqueue = function (ele) {
		//TODO
	}
}

const queue = new Queue()

function passGame(nameList, num) {

}

优先级队列

数组实现

function PriorityQueue() {
	//优先级队列元素 包含内容及优先级系数 -> 创建内部类
	function QueueElement(ele, zindex) {
		this.ele = ele;
		this.zindex = zindex;
	}
	
	this.arr = [];
	
	//插入
	PriorityQueue.prototype.enqueue = function (element, index) {
		//创建队列元素对象
		const queueElement = new QueueElement(element, index);

		//1.队列为空直接入队
		//2.根据优先级然后插入
		//TODO
	}
	
}

链表

链表优点：

• 内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理.
• 链表不必在创建时就确认大小，并且大小可以无限的延伸下去.
• 链表在插入和删除数据，时间复杂度可以达到O(1).
• 无法通过下标直接访问，需要从头一个个访问。

单向链表：链表相连的过程中时单向的。

链表的常见操作

• append：向列表位置添加一个元素
• insert：向列表的特定位置插入一个新的项
• get：获取对应位置的元素
• indexOf：返回元素在列表的索引。
• update：修改某个位置的元素
• removeAt: 从列表的特定位置移除一项
• remove: 从列表中移除一项
• isEmpty：是否为空
• size：返回链表包含元素个数
• toString：输出元素值

封装链表

function LinkedList() {
	function Node(data){
		this.data = data;
		this.next = null
	}

	this.head = null;
	this.length = 0;

	LinkedList.prototype.append = function (data){
		const newNode = new Node(data)
		//1.有节点 2.无节点
		if(this.length === 0){
			this.head = newNode
		}else {
			let current = this.head;
			while(current.next){
				current = current.next
			}

			current.next = newNode
		}

		this,length += 1
	}

	LinkedList.prototype.insert = function (position, data){
		//1.边界判断
	}

}

双向链表

• head：头指针
• tail：尾指针
• prev：指向上一个节点
• next：指向下一个节点

封装双向链表

function DoulyLinkedList(){
	
}

树

二叉树：树中每个节点最多只能有两个子节点。

二叉树的特性

• 一个二叉树第 i 层的最大节点数为： 2^(i - 1), i ≥ 1;
• 深度为K的二叉树有最大节点总数为：2^k - 1, k ≥ 1;
• 对任何非空二叉树T，若n0表示叶节点的哥数、n2是度为2的非叶子节点合格数，那么两者满足关系n0 = n2 + 1

完全二叉树：除叶子节点都是满的

树的遍历方式

先序遍历

1. 访问根节点
2. 先序遍历其左子树
3. 先序遍历其右子树

中序遍历

1. 中序遍历其左子树
2. 访问根节点
3. 中序遍历其右子树

后序遍历

1. 后序遍历其左子树
2. 后序遍历其右子树
3. 访问根节点

二叉搜索树

常见方法：

• insert：向树中插入一个新的键
• search：查找一个键
• inOrderTraverse：通过中序遍历方式遍历所有节点
• preOrderTraverse：通过先序遍历方式遍历所有节点
• postOrderTraverse：通过后序遍历方式遍历所有节点
• min：返回树中最小值
• max：返回树中最大值
• remove：删除某个键

封装二叉搜素树

function BinarySerachTree() {
	function Node(key) {
	
	}

	this.root = null

}

对于一颗平衡二叉树来说，插入、查找等操作的效率是O(logN)

对于一颗非平衡二叉树，相当于编写了一个链表，查找效率是O(N)