JavaScript数据结构与算法 -- 顺序栈篇

名词注释

栈顶
栈底
出栈
入栈
先进后出 FILO (First in last out)

JavaScript数据结构与算法顺序栈篇-2023-11-30-14-55-16

我们知道，可以在数组的任意位置上删除或添加元素。然而，有时候还需要一种能在添加或删除元素时进行更多控制的数据结构。有两种类似于数组的数据结构在添加和删除元素时更为可控，它们就是栈和队列。

本文章内容学习栈，内容包括：

栈数据结构库
向栈添加元素
从栈移除元素
如何使用Stack 类
简单路由
十进制转二进制

一、什么是栈

栈是数据结构中的一种重要的线性结构，也是一种线性表，只是其操作受限。
使用的过程，就像往桶里装和取物品一样，最先放进去的物品必须把后来放进去的压在上面的物品拿出去，才能取出。
因此，栈是一种限定性的数据结构，其广泛应用与各类软件系统中。

从实现上栈分为两种：

顺序栈
链式栈

顺序栈

顺序栈是栈的一种存储表示方法。类似顺序表，顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素的一种存储，同时有指针 top 指示栈顶元素在顺序栈中的位置。通常，使用 top=0 表示空栈。一般来说，使用栈时，先给其分配一个基本容量，当空间不够时，再逐渐扩大。

此文也以顺序栈展开

链式栈

链式栈是通过单链表来实现的。每次入栈一个元素，向链表中添加一个节点，出栈一个元素，释放一个节点。因为栈具有“后进先出”的特点，如果每次在链表的尾部进行插入和删除，就要遍历整个链表来找到尾节点。而在头部进行插入和删除时，只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出，入栈通过对链表进行头删和头插来实现。

二、特点

栈是一种遵从先出后进 （FILO）原则的有序集合。
新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈(Stack)作为一种线性表，它仅能在表尾进行插入和删除操作，因此表尾被称作栈顶，表头被称为栈底。栈的数据元素的进出满足“FILO”的原则。没有任何元素的空表被称为空栈。

三、栈操作

栈的最基本操作有二：

入栈（Push）
出栈（Pop）

除此之外，还具有栈的初始化、判断是否为空、取栈顶元素等多种操作。

根据这些操作基本可将栈抽象为：

1
2
3
4
5
6
7
8
interface IStack {
    push: (el: number | number[]) => void
    pop: () => number
    peek: () => number
    isEmpty: () => boolean
    clear: () => void
    size: () => number
}

四、javascript 实现一个栈

我们需要一种数据结构来保存栈里的元素，数组做为最简单的内存数据结构，提供不少方便方法操作，所以选择数组来存储。
由于栈的 LIFO 原则，要对元素的部分操作进行限制。

数组中栈表示为:

栈顶: 即是下标为[length-1]的元素
栈底: 即是下标为[0]的元素

一个基于数组的栈

先是一个数组用来作为存储元素的结构

1
2
3
4
5
class Stack {
  constructor() {
    this.items = [];
  }
}

实现向栈添加元素(入栈)

添加 push 方法，该方法负责往栈里添加新元素。
有一点很重要：该方法只添加元素到栈顶，也就是栈的末尾

push 方法可以如下这样写。

1
2
3
push(element) {
    this.items.push(element);
}

实现从栈顶删除元素(出栈)

1
2
3
pop() {
    return this.items.pop();
}

由于数组的push与pop操作就是对栈的末尾元素操作，所以这样就遵从了 LIFO 原则

查看栈顶元素

1
2
3
peek() {
    return this.items[this.items.length - 1];
}

检查栈是否为空

粗略的以 length 来判断是不是空的栈

1
2
3
isEmpty() {
    return this.items.length === 0;
}

对于元素的大小也可以简单的这样实现

1
2
3
size(){
    return this.items.length;
}

清空元素

1
2
3
clear(){
    this.items = [];
}

到这里，一个简单的栈就已经实现了。

五、应用

单页面应用的路由采用栈结构
栈可以用来在函数调用的时候存储断点，做递归时要用到栈！

六、实例

使用 vue 实现一个简单的页面路由功能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
<template>
  <div class="stack">
    <div class="back" @click="back">back</div>
    <div class="page" v-if="currentPage == 'base'">base content</div>
    <div class="page" v-if="currentPage == 'page1'">
      page 1 content
      <div @click="toPage('page2')">to page 2</div>
    </div>
    <div class="page" v-if="currentPage == 'page2'">
      page 2 content
      <div @click="toPage('page3')">to page 3</div>
    </div>
    <div class="page" v-if="currentPage == 'page3'">page 3 content</div>
  </div>
</template>

 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
<script>
import Stack from '../utils/Stack';
export default {
  name: 'home',
  data() {
    return {
      currentPage: ''
    };
  },
  created() {
    Stack.push('base');
    Stack.push('page1');
  },
  mounted() {
    this.currentPage = Stack.peek();
  },
  components: {},
  methods: {
    back() {
      Stack.pop();
      if (Stack.size() < 1) return;
      this.currentPage = Stack.peek();
    },
    toPage(page) {
      console.log('to:', page);
      Stack.push(page);
      this.currentPage = Stack.peek();
    }
  }
};
</script>

使用 push 入栈默认显示的页面与首页

1
2
3
4
created() {
  Stack.push('base');
  Stack.push('page1');
}

之后每次打开新页面时使用 Stack.push(page); 入栈页面

1
2
3
4
toPage(page) {
  Stack.push(page);
  this.currentPage = Stack.peek();
}

下图描绘了我们对栈的操作，以及栈的状态。
JavaScript数据结构与算法顺序栈篇-2023-11-30-14-55-45

使用 pop 出栈

1
2
3
4
5
back() {
  Stack.pop();
  if (Stack.size() < 1) return;
  this.currentPage = Stack.peek();
}

出栈的操作，以及栈的状态图。

JavaScript数据结构与算法顺序栈篇-2023-11-30-14-55-53

每次对栈操作过后获取栈顶页面的地址并显示

1
this.currentPage = Stack.peek();

从十进制到二进制

JavaScript数据结构与算法顺序栈篇-2023-11-30-14-55-57

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = "";

  while (number > 0) {
    // {1}
    rem = Math.floor(number % 2); // {2}
    remStack.push(rem); // {3}
    number = Math.floor(number / 2); // {4}
  }

  while (!remStack.isEmpty()) {
    // {5}
    binaryString += remStack.pop().toString();
  }

  return binaryString;
}

在这段代码里，当除法的结果不为 0 时（行{1} ），我们会获得一个余数，并放到栈里（行{2} 、行{3} ）。然后让结果继续除以 2（行{4} ）。另外请注意：JavaScript 有数值类型，但是它不会区分整数和浮点数。因此，要使用Math.floor 函数仅返回除法运算结果的整数部分。最后，用pop 方法把栈中的元素都移除，把出栈的元素连接成字符串（行{5} ）。

七、源码

class Stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Stack {
  constructor() {
    this.items = []; // {1}
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
  clear() {
    this.items = [];
  }
}

stack.vue

 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
<template>
  <div class="stack">
    <div class="back" @click="back">back</div>
    <div class="page" v-if="currentPage == 'base'">base content</div>
    <div class="page" v-if="currentPage == 'page1'">
      page 1 content
      <div @click="toPage('page2')">to page 2</div>
    </div>
    <div class="page" v-if="currentPage == 'page2'">
      page 2 content
      <div @click="toPage('page3')">to page 3</div>
    </div>
    <div class="page" v-if="currentPage == 'page3'">
      page 3 content
    </div>
  </div>
</template>

<script>
import Stack from '../utils/Stack';
export default {
  name: 'home',
  data() {
    return {
      currentPage: ''
    };
  },
  created() {
    Stack.push('base');
    Stack.push('page1');
  },
  mounted() {
    this.currentPage = Stack.peek();
  },
  components: {},
  methods: {
    back() {
      Stack.pop();
      if (Stack.size() < 1) return;
      this.currentPage = Stack.peek();
    },
    toPage(page) {
      console.log('to:', page);
      Stack.push(page);
      this.currentPage = Stack.peek();
    }
  }
};
</script>