什么是数据结构和算法?

1/8/2021 JavaScriptAlgorithm

# 文章目录

# 一、什么是数据结构?

简单点来说:数据结构就是在计算机中存储和组织数据的方式。

# 2.1 为什么需要数据结构?

计算机中存储的数据量相对来说数据量更大,数据种类更多

以什么样的方式来存储和组织我们的数据,才能在使用数据时更加方便呢?
这就是数据结构需要考虑的问题。

# 2.2 常见的数据结构

在这里插入图片描述

常见的数据结构较多

  • 每一种都有其对应的应用场景,不同的数据结构的不同操作性能是不
    同的
  • 有的查询性能很快,有的插入速度很快,有的是插入头和尾速度很快
  • 有的做范围查找很快,有的允许元素重复,有的不允许重复等等
  • 在开发中如何选择要根据具体的需求来选择

# 二、什么是算法 Algorithm?

在解决问题的过程中,不仅数据的存储方式会影响效率(数据结构),算法的优劣也会影响效率。

算法大意为:解决问题的步骤、逻辑、或一步步的操作。

在这里插入图片描述

# 三、数组结构 Array

数组是一种线性结构,并且可以在数组的任意位置插入和删除数据。

  • 常见语言的数组不能存放不同的数据类型,因此所有在封装时通常存放在数组中的是 Object 类型。
  • 常见语言的数组容量不会自动改变。(需要进行扩容操作)。
  • 常见语言的数组进行中间插入和删除缲作性能比较低。

# 四、栈结构 Stack

# 4.1 什么是栈?

在这里插入图片描述

# 4.2 栈结构示意图

在这里插入图片描述

# 4.3 栈的

在这里插入图片描述

# 4.4 面试题

在这里插入图片描述
答案是:C

# 4.5 栈结构的实现

实现栈结构有两种比较常见的方式:

  • 基于数组实现
  • 基于链表实现

什么是链表?

  • 也是一种数据结构,目前我们还没有学习,并且 JavaScript 中并没有自带链表结构
  • 后续,我们会自己来实现链表结构,并且对比数组和链表的区别。

因此,我们这里实现的栈结构基于数组

# 4.5.1 栈的常见方法

  • push() 添加一个新元素到栈顶位置
  • pop() 移除栈顶的元素,同时返回被移除的元素。
  • peek() 返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)
  • isempty() 如果栈里没有任何元素就返回 true,否则返回 false.
  • size() 返回栈里的元素个数。这个方法和数组的 length 属性很类似。
  • toString() 将桟结构的内容以字符形式返回

现在,我们可以在类中一一实现这些方法。

先搭建基本框架:

<script>
  // 封装我们的栈类 function Stack(){" "}
  {
    // 栈中的属性
    (this.items = [])

    // 栈的相关操作
  }
  // 栈的使用 var s = new Stack()
</script>
1
2
3
4
5
6
7
8
9
10

实现基本方法:

<script>
  // 封装我们的栈类
  function Stack() {
    // 栈中的属性
    this.items = []

    // 栈的相关操作

    // 1.将元素压入栈
    Stack.prototype.push = function (element){
      this.items.push(element)
    }

    // 2.从栈顶中取出元素
    Stack.prototype.pop = function (){
      return this.items.pop()
    }

    // 3.查看栈顶元素
    Stack.prototype.peek = function (){
      return this.items[this.items.length - 1]
    }

    // 4.判断栈是否为空
    Stack.prototype.isEmpty = function (){
      return this.items.length == 0
    }
    // 5.获取栈中的元素个数
    Stack.prototype.size = function (){
      return this.items.length
    }
    // 6.toString方法
    Stack.prototype.toString = function (){
      let resultString = ''
      for(let i = 0;i<this.items.length;i++){
        resultString += this.items[i] + ' '
      }
      return resultString
    }
  }

  // 栈的使用
  var s = new Stack()
  s.push(20)
  s.push(10)
  s.push(100)
  s.push(77)
  alert(s);

  s.pop()
  s.pop()
  console.log(s);


  console.log(s.peek());

  console.log(s.isEmpty());

  console.log(s.size());

  console.log(s.toString());
</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
58
59
60
61
62

# 4.6 使用栈实现十进制转二进制

我们已经学会了如何使用 Stack 类,现在就用它解決一些计算机科学中的问题。

在平时我们都是怎么把十进制转化为二进制的呢?

答案是:余数倒排法
在这里插入图片描述
在这里插入图片描述
用栈的方法来实现十进制转二进制:
注意:Stack 类在 4.5.1 已经实现,这里不再贴出代码

// decimal 十进制  binary 二进制
function dec2bin(decNumber) {
  // 1. 定义栈对象 对于保存余数
  let stack = new Stack();

  // 2.循环操作
  while (decNumber > 0) {
    // 2.1 获取余数,并且放入到栈中
    stack.push(decNumber % 2);

    // 2.2 获取整除后的结果,作为下一次运算的数字
    decNumber = Math.floor(decNumber / 2);
  }

  // 3.从栈中取出0和1
  let binaryString = "";
  while (!stack.isEmpty()) {
    binaryString += stack.pop();
  }
  return binaryString;
}

// 测试十进制转化为二进制
console.log(dec2bin(52)); // 110100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
最后更新于: 2021年9月15日星期三晚上10点10分
Faster Than Light
Andreas Waldetoft / Mia Stegmar