栈(stack)又名堆栈,它是一种运算受限的线性表。特点是先进后出(FILO),限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

——百度百科

了解了栈结构的特点,接下来就是实现它了,首先我们封装一个栈类,如下:

class Stack {
 constructor(){
 this.items = new Array();
 }
}

然后我们来一一实现栈结构的方法。

push():把元素压入栈顶

//el就是传入的元素
push(el){
 this.items.push(el)
}

pop():删除并返回栈顶的元素

pop(){
 return this.items.pop()
}

peek():获取栈顶的元素

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

isEmpty():查看栈是否为空

isEmpty(){
 return this.items.length === 0
}

size():返回栈的长度

size(){
 return this.items.length
}

toString():将栈中的所有元素以字符串的形式返回

toString(){
 let res = new String();
 for(let i = 0; i < this.items.length; i++){
  res = res + this.items[i] + " "
 }
 return res
}

clear():清空栈内所有元素

clear(){
 this.items = new Array()
}

实际应用:十进制转换二进制

举个例子,数字10转换为二进制,过程大致如下:

10 / 2 = 5,余数为0

5 / 2 = 2,余数为1

2 / 2 = 1,余数为0

1 / 2 = 0, 余数为1

我们将上述每一步的余数颠倒顺序排列起来,就得到转换之后的结果:1010。

按照这个逻辑,我们可以这样写:

function decToBin(decNumber) {
 let s = new Stack();//创建一个栈的实例
 while(decNumber > 0){
  s.push(decNumber % 2)//把传入数字除以二的余数压入栈
  decNumber = parseInt(decNumber / 2)//每循环一次传入数字都要除以2
 }
 let res = new String();
 while(!s.isEmpty()){
  res = res + s.pop();//依次弹出栈中的元素并组成一个字符串
 }
 return res;//返回结果
}
console.log(decToBin(10))//调用函数,返回“1010”

以上,栈的实现与应用~

               

作者