什么是数据结构？

不同的书对数据结构有不同的定义，例如：

• “数据结构是数据对象，以及存在于该对象的实例和 组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。” — 《数据结构、算法与应用》
• “数据结构是ADT（抽象数据类型 Abstract Data Type）的物理实现。” — 《数据结构与算法分析》
• “数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以 带来最优效率的算法。” —中文维基百科

虽然定义有所差别但其实本质核心是不变的，都是在计算机中, 存储和组织数据的方式

常见的数据结构

常见的数据结构其实还蛮多的，大致有栈、队列、链表、集合、字典、树等等
每种结构都有自己的特点，有的查询速度很快，有的插入速度很快，有的做范围查找很快，反正每一种结构都是有自己的优势的，具体场景的使用需要具体的分析

算法

算法通常是与数据结构联系在一起的，我们说到数据结构就会想到算法，不同的算法会影响同一件事的执行效率，所以算法越好，执行的速度就越快

那么什么是算法呢？算法就是
一个有限指令集, 每条指令的描述不依赖于语言
接受一些输入（有些情况下不需要输入）
产生输出
一定在有限步骤之后终止

数据结构的实现, 是离不开算法的

数据结构之栈

什么是栈？

栈（stack），它是一种运算受限的线性表示，后进先出(LIFO)或者说先进后出

• LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空
• 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
• 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
• 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的常用方法

• push(element): 添加一个新元素到栈顶位置
• pop()：移除栈顶的元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）
• isEmpty()：如果栈里没有任何元素就返回true，否则返回false
• clear()：移除栈里的所有元素
• size()：返回栈里的元素个数，这个方法和数组的length属性很类似

接下来我们就来封装一下这些常用的方法吧

<script>
	class Stack {
	    constructor() {
	    	// 创建一个空数组，来存放添加的元素
	        this.item = []
	    }
	    
	    // 1.向栈顶添加元素   数组的最后添加元素
	    push(ele) {
	        this.item.push(ele)
	    }
	
	    // 2.移除栈顶元素,返回栈顶元素(数组最后一个元素)
	    pop() {
	        let delnode = this.item.pop();
	        return delnode
	    }
	
	    // 3.返回栈顶元素(数组最后一个元素)
	    peek() {
	        let index = this.item.length - 1;
	        return this.item[index]
	    }
	
	    // 4.判空 栈为空true  数组的length长度来判断栈是否为空
	    isEmpty() {
	        return this.item.length == 0;
	    }
	
	    // 5.清空栈
	    clear() {
	        this.item = [];
	    }
	
	    // 6.栈元素的个数 == 数组中元素的个数
	    size() {
	        return this.item.length
	    }
	}
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

栈就封装好啦，需要用的时候直接使用script：src调用就好了

栈的实例

十进制转为二进制，八进制，十六进制

这里的代码量不算多，我也就没有去调用上面封装的方法，就直接自己写的

<script>
	// 创建一个空数组，来装添加的内容
   var arr = [];
   // 传入需要转换的数和转换的进制
   function change(chushu, base) {
   		// 为了符合十六进制的表示形式
       let arr1 = ["A", "B", "C", "D", "E", "F"];
       while (chushu > 0) {
           let yushu = chushu % base;
           if (yushu > 9) {
               arr.push(arr1[yushu - 10])
           } else {
               arr.push(yushu)
           }
           var chushu = Math.floor(chushu / base);
       }
       var str = "";
       while (!arr.length == 0) {
           str +=  arr.pop();
       }
       return str;
   }
   console.log(change(100, 2));
   console.log(change(10, 2));
   console.log(change(10, 8));
   console.log(change(30, 16));
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

执行结果

大家可以自己去用计算检测一下转换的对不对

数据结构之队列

什么是队列？

队列(Queue)，和栈一样是一种运算受限的线性表,先进先出(FIFO First In First Out)或者后进后出

• 队列是一种受限的线性结构
• 受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

队列的常用方法

• enqueue(element)：向队列尾部添加一个（或多个）新的项
• dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
• front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）
• isEmpty()：如果队列中不包含任何元素，返回true，否则返回false
• size()：返回队列包含的元素个数，与数组的length属性类似

现在同样的我们来封装一下这些常用的方法

<script>
	class Queue{
       constructor(){
           this.item = [];
       }
       
       // 1.入队
       enqueue(ele){
           this.item.push(ele)
       }

       // 2.出队
       delqueue(){
           return this.item.shift()
       }

       // 3.返回队首元素
       front(){
           return this.item[0]
       }

       // 4.判空
       isEmpty(){
           return this.item.length == 0
       }

       // 5.y元素的个数
       size(){
           return this.item.length
       }
   }
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

封装完成，使用的时候同栈的封装方法一样直接调用就可以了

来看一个实例叭

实例

击鼓传花

这个游戏规则是，给每个数据标号，标号为3的那个一个数据出栈了就不在进栈了，其余1,2的出栈了需要进栈，一直这样循环，直到队列里面只剩一个数据，那么这个数据就是最后的赢家，我们来看看代码吧

<script src="Queue.js"></script>
<script>
    function jigu(arr) {
        // 创建队列
        let queue = new Queue();
        // 依次入队
        arr.forEach(ele => {
            queue.enqueue(ele)
        });

        // 标号
        let count = 1;
        while (queue.size() > 1) { 
            if (count < 3) {
                let node = queue.delqueue(); 
                queue.enqueue(node); 
                count++;
            } else {
                queue.delqueue(); 
                count = 1
            }
        }
        // 获胜者和在原数组中的位置
        return {
            winner: queue.front(),
            position: arr.indexOf(queue.front())
        }
    }
    var arr = ["任嘉伦", "杨洋", "魏晨", "刘昊然", "戚薇", "张若昀", "黄蓉"];
    console.log(jigu(arr));
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

执行结果

优先级队列

上面介绍的一种是普通队列，还有一种比较特殊的队列，就是优先级队列

优先级队列的特点:

• 普通的队列插入一个元素, 数据会被放在后端，并且需要前面所有的元素都处理完成后才会处理前面的数据
• 但是优先级队列,，在插入一个元素的时候会考虑该数据的优先级 (和其他数据优先级进行比较)
• 比较完成后，可以得出这个元素正确的队列中的位置，其他处理方式,，和队列的处理方式一样

优先级队列的实现

实现优先级队列相对队列主要有两方面需要考虑:

1. 封装元素和优先级放在一起(可以封装一个新的构造函数)
2. 添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置

<script>
	function PriorityQueue() {
	    var items = []
	
	    // 封装一个新的构造函数, 用于保存元素和元素的优先级
	    function QueueElement(element, priority) {
	        this.element = element
	        this.priority = priority
	    }
	
	    // 添加元素的方法
	    this.enqueue = function (element, priority) {
	        // 1.根据传入的元素, 创建新的QueueElement
	        var queueElement = new QueueElement(element, priority)
	
	        // 2.获取传入元素应该在正确的位置
	        if (this.isEmpty()) {
	            items.push(queueElement)
	        } else {
	            var added = false
	            for (var i = 0; i < items.length; i++) {
	                // 注意: 我们这里是数字越小, 优先级越高
	                if (queueElement.priority < items[i].priority) {
	                    items.splice(i, 0, queueElement)
	                    added = true
	                    break
	                }
	            }
	
	            // 遍历完所有的元素, 优先级都大于新插入的元素时, 就插入到最后
	            if (!added) {
	                items.push(queueElement)
	            }
	        }
	    }
	
	    // 删除元素的方法
	    this.dequeue = function () {
	        return items.shift()
	    }
	
	    // 获取前端的元素
	    this.front = function () {
	        return items[0]
	    }
	
	    // 查看元素是否为空
	    this.isEmpty = function () {
	        return items.length == 0
	    }
	
	    // 获取元素的个数
	    this.size = function () {
	        return items.length
	    }
	}
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

其实与普通队列相比也就多了几行确定优先级和位置的代码，其他的基本是一样