数据结构之栈结构

基本定义：

只允许在有序的线性资料集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。它有两种基本操作：推入或者弹出，遵循着先入后出，后入先出的特点。

在javascript中实现栈结构

在javascript中实现栈结构，最常见的就是借助数组来实现，数组中提供了push和pop方法，可以很轻松的实现栈结构的特点。

栈结构的常用操作

  1. push：添加一个新元素到栈顶

  2. pop：移除栈顶的元素，同时返回被移除的元素

  3. peek：返回栈顶的元素，不对栈做任何修改，单纯的看一眼栈顶是谁

  4. isEmpty：如果栈里没有元素就返回true，反之返回false

  5. size：返回栈里元素的个数

  6. toString：将栈结构的内容以字符串的形式返回

利用数组实现栈结构

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
class Stack {
  constructor() {
    this.items = [];
  }
  push(item) {
    this.items.push(item);
  }
  pop(item) {
    return this.items.pop(item);
  }
  peek() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length > 0 ? false : true;
  }
  size() {
    return this.items.length;
  }
  toString() {
    let str = "";
    this.items.forEach(item => {
      str = str + item + " ";
    });
    return str;
  }
}

const stack = new Stack();

实现十进制转换成二进制

在实现之前要了解一点理论知识，十进制转换成二进制是怎么转换的？如果过程都不知道，自然不可能将其转换为代码了。

十进制是我们日常生活中最常见的，二进制则是我们计算机底层的实现，类似于电路的开和关，也就对应着0和1，比如说100我们该如何转换成二进制呢？首先我们将100除于2然后去余数，然后得到50和余数0，然后继续拿50除于2，得到25和余数0，继续拿25除于2，得到12.5和余数1，12.5我们直接向下取整，得到12，然后继续拿12除于2，得到6和余数0，以此类推，最后我们反向将得到的余数拼在一起，最后得到110 0100。

既然知道了十进制转换成二进制的过程，接下来我们用代码对其进行复现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function dec2bin(number) {
  const stack = new Stack();
  // 只要number> 0就继续求余数
  while (number > 0) {
    stack.push(number % 2);
    number = Math.floor(number / 2);
  }
  //从栈中挨个取出元素，然后拼接在一起
  let bin = "";
  while (!stack.isEmpty()) {
    bin += stack.pop();
  }
  return bin;
}