文章目录

• 一、什么是数据结构？
  • 2.1 为什么需要数据结构？
  • 2.2 常见的数据结构
• 二、什么是算法 Algorithm？
• 三、数组结构 Array
• 四、栈结构 Stack
  • 4.1 什么是栈？
  • 4.2 栈结构示意图
  • 4.3 栈的
  • 4.4 面试题
  • 4.5 栈结构的实现
    • 4.5.1 栈的常见方法
  • 4.6 使用栈实现十进制转二进制

一、什么是数据结构？

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

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>

实现基本方法：

<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>

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