堆栈的基础知识

栈

  • 什么是栈

  • 栈的操作

  • 实现一个栈类

  • 栈的应用

  • 栈属性私有化

什么是栈

image
堆栈是只能从列表的一端(称为顶部)访问的元素列表. 一个常见的，现实生活中的例子就是自助餐厅的托盘堆. 托盘总是从顶部取走, 当托盘在清洗后放回堆栈时，它们被放置在堆栈的顶部. 堆栈被称为后进先出(LIFO)数据结构.

由于堆栈的后进先出特性, 当前不在栈顶都不能被访问的. 假如想访问栈底的元素必须把上面的元素移除(托盘取走)

栈是一种类队列的数据结构, 可以用解决许多计算问题. 同时栈是非常高效的一种数据结构，因数据新增、删除都只能从栈顶完成, 并且容易以及快速实现.

栈操作

由于栈后入先出的特性，任何非栈顶元素不能被访问. 要想访问栈底的元素必须把上面的元素全部出栈才能访问到.

下面栈的常用的两个操作，元素入栈、出栈. 使用push操作将元素添加到堆栈中, 使用pop操作从堆栈中取出元素. 下图所示
image

堆栈另一个常见操作是查看堆栈顶部的元素. pop操作访问堆栈的顶部元素，但是它将永久地从堆栈中删除该元素. peek操作返回存储在堆栈顶部的值，而不从堆栈中删除它. 除pop()、push()、peek() 主要方法外, 栈应该包含其它的如判断栈是不是空 isEmpty()、获取栈的大小 size()、清空栈 clear().
下面通过代码来实现一个栈.

栈的实现

通过数组来实现一个栈, 代码如下:

class Stack {
constructor() {
this.items = []
}
push(ele) {
this.items.push(ele)
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1]
}
isEmpty() {
return !!this.items.length
}
size() {
return this.items.length
}
clear() {
this.items = []
}
print(){
return this.items.toString()
}
}

下面通过一个案例来测试下定义栈类.

const stack = new Stack()
console.log(stack.isEmpty()) //=> true
stack.push(1) //=> 入栈 1
stack.push(2) //=> 入栈 2
stack.push(3) //=> 入栈 3
stack.pop()   //=> 出栈 3
stack.pop()   //=> 出栈 2
stack.push(4) //=> 入栈 4
console.log(stack.isEmpty()) //=> false
console.log(stack.size());   //=> 2
stack.clear();
console.log(stack.isEmpty()); //=> true

上面代码只是简单操作,这里就不一一介绍了.

栈的应用

下面通过几个实际的例子来增加我们对栈的理解：

进制转换

把一个数字从一个基数转为另外一个基数. 给定一个数字 n, 要把它转为基数b, 下面大概的步骤:

  1. n % b 取余推入栈中

  2. n / b 取模后的值替换 n 值

  3. 重复步骤1、2，直到 n = 0

  4. 通过出栈操作获取转换后字符串

进制转换，通过栈非常容易实现，下面大概实现方式

function baseConverter(num, base) {
const stack = new Stack()
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
if(!(base >= 2 && base <= 32)){
return '';
}
do {
stack.push(num % base)
num = Math.floor(num / base)
} while (num > 0)
let converted = ''
while (!stack.isEmpty()) {
converted += digits[stack.pop()]
}
return converted;
}

下面我们来测试下: 把一个数字转为二进制、八进制

let num = 32
let base = 2
let converted = baseConverter(num, base)
console.log(`${num} converted to base ${base} is ${converted}`)
num = 125
base = 8
converted = baseConverter(num, base)
console.log(`${num} converted to base ${base} is ${converted}`)

运行输出后结果为:

回文

什么是回文:

我们可以使用堆栈来确定给定的字符串是否是回文. 拿到

  • 把字符串中的每个字符压入到栈中

  • 通过 pop() 方法生成新的字符串

  • 拿原字符串与新生成的字符串比较，相同则为“回文”

image

下面通过代码实现判断回文的方法:

function isPalindrome(word) {
const stack = new Stack()
for (let i = 0; i < word.length; i++) {
stack.push(word[i])
}
let rword = ''
while (!stack.isEmpty()) {
rword += stack.pop()
}
return word === rword
}
console.log(isPalindrome('racecar')) // true
console.log(isPalindrome('hello'))   // false

注意
实现判断回文方式很多, 这里只是列举通过栈如何实现

用堆栈模拟递归过程

演示如何用堆栈实现递归，就以阶乘为例.

  5！= 5 * 4 * 3 * 2 * 1 = 120

先用递归方法实现, 具体如下：

function factorial(n) {
if (n === 1) {
return 1
} else {
return n * factorial(n-1)
}
}

👇使用堆栈模拟递归过程:

function fact(n) {
const stack = new Stack()
while (n > 1) {
stack.push(n--)
}
let product = 1
while (!stack.isEmpty()) {
product *= stack.pop()
}
return product
}

栈属性私有化

私有化实际就是隐藏内部细节，只对外提供操作方法，这样能保证代码安全性. 下面常用方式:

  • 命名约定方式

class Stack {
constructor() {
this._items = []
}
}

这种方式只是一种约定并不能起到保护作用，而且只能依赖使用我们代码的开发者所具备的常识.

  • 借助ES模块作用域和 Symbol 属性

const _items = Symbol('stackItems')
class Stack {
constructor() {
this[_items] = []
}
}
//...

}
这种方式其实创建一个假的私有属性, ES2015新增的Object.getOwnPropertySymbols方法能取到类里面声明的所有 Symbol 属性, 下面是破坏Stack类的例子

const stack = new Stack()\
stack.push(1)
stack.push(2)
let objectSymbols = Object.getOwnPropertySymbols(stack)
console.log(objectSymbols.length) // 1
console.log(objectSymbols) // [ Symbol(stackItems) ]
console.log(stack[objectSymbols[0]].push(1))
console.log(stack.print()) // 1,2,1

  • 利用 WeakMap 来实现是私有化

const items = new WeakMap()
class Stack {
constructor() {
items.set(this, [])
}
push(ele) {
const s = items.get(this)
s.push(ele)
}
pop() {
const s = items.get(this)
const r = s.pop()
return r
}
}

items 在 Stack 类里是真正的私有属性. 采用这种方式带来问题代码可读性不强，而且扩展该类时无法继承私有属性.

  • ECMAScript 类属性提案

虽然在 TypeScrpit 中存在通过 private 修饰符来定义私有变量, 但是这只能编译时才有效，在编译后还是可以被外部访问.

在ES草案中提供如下方式进行声明私有化属性

class Stack {
#items = [];
push(ele) {
// 访问
this.#items.push(ele)
}
}

详细

以上是 堆栈的基础知识 的全部内容， 来源链接： utcz.com/a/44209.html

回到顶部