1. 列表项目

栈是一种后进先出(LIFO)的数据结构，我们所能操作的都是栈顶元素，删除一个栈顶元素叫做出栈或者弹栈，添加一个元素叫做入栈或者压栈.

ADT

首先构建我们的抽象数据类型.

Stack;
top; // 栈顶元素位置
dataStore; //保存数据的数组
push; // 压栈
pop; // 出栈
peek; // 查看栈顶元素
empty; // 清空栈
length; // 栈的长度
print; // 输出栈元素

Javascript 描述

function Stack() {
  this.top = 0;
  this.dataStore = [];
}
Stack.prototype = {
  constructor: Stack,
  push: function (element) {
    return (this.dataStore[this.top++] = element);
  },
  pop: function () {
    return this.dataStore.length ? this.dataStore.splice(--this.top, 1) : false;
  },
  peek: function () {
    return this.dataStore[this.top - 1];
  },
  empty: function () {
    this.dataStore.length = 0;
  },
  length: function () {
    return this.dataStore.length;
  },
  // 模拟输出栈结构
  print: function () {
    for (var i = this.length() - 1; i >= 0; i--) {
      console.log(this.dataStore[i] + '\n');
    }
  },
};

测试

var stack = new Stack();
// 入栈
stack.push('jiavan');
stack.push('jiavan2');
stack.push('jiavan3');
stack.push('jiavan4');

// jiavan4
// jiavan3
// jiavan2
// jiavan
stack.print();

// jiavan4
stack.pop();
// jiavan3
stack.peek();
// 3
stack.top;
// jiavan3
// jiavan2
// jiavan
stack.print();

应用

对 num 数进行 n 进制的转换，大致算法如下：

  • 对 num 和 n 进行求余和想除取整
  • 将余数入栈 push
  • 回到第一步直至除到值为 0
function transformNum(num, base) {
  var res = parseInt(num / base);
  var stack = new Stack();
  stack.push(num % base);
  while (parseInt(res)) {
    stack.push(parseInt(res % base));
    res /= base;
  }
  stack.print();
}

// transformNum(10, 2)， 1010
// transformNum(10, 8)， 12

栈的应用还有很多，比如匹配括号以及表达式求值等等.

系列文章原文地址https://github.com/Jiavan/js4algs GitHub repo 上有源码和更好的阅读体验，若有错误欢迎发 PR，若对你有所帮助也欢迎 star!