线性表-栈

知识库大约 2 分钟

栈是是一种特殊的线性表，仅能够在栈顶操作数据，其特点是先进后出（后进先出）

栈的实现

// javascript的栈实现
function Stack() {
  var items = [];
  // ⽅法向栈⾥压⼊⼀个元素
  this.push = function (item) {
    items.push(item);
  };
  // ⽅法把栈顶的元素弹出
  this.pop = function () {
    return items.pop();
  };
  // ⽅法返回栈顶元素
  this.top = function () {
    return items[items.length - 1];
  };
  // 返回栈是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };
  // ⽅法返回栈的⼤⼩
  this.size = function () {
    return items.length;
  };
  // 清空栈
  this.clear = function () {
    items = [];
  };
}

基于链表实现栈

function Stack() {
  var linklist = new LinkList();
  // 从栈顶添加元素
  this.push = function (item) {
    linklist.append(item);
  };
  // 弹出栈顶元素
  this.pop = function () {
    return linklist.remove_tail();
  };
  // 返回栈顶元素
  this.top = function () {
    return linklist.tail();
  };
  // 返回栈的⼤⼩
  this.size = function () {
    return linklist.length();
  };
  // 判断是否为空
  this.isEmpty = function () {
    return linklist.isEmpty();
  };
  // 清空栈
  this.clear = function () {
    linklist.clear();
  };
}

栈的应用

合法括号

请编写函数判断字符串中的括号是否合法，所谓合法就是括号成对出现。
sdf(ds(ew(we)rw)rwqq)qwewe      合法
(sd(qwqw)sd(sd))                合法
()()sd()(sd()fw))(              不合法

实例代码

function is_leagl_brackets(string) {
  var stack = new Stack();
  for (var i = 0; i < string.length; i++) {
    var item = string[i];
    if (item == "(") {
      // 将左括号压⼊栈
      stack.push(item);
    } else if (item == ")") {
      // 如果为空,就说明没有左括号与之抵消
      if (stack.isEmpty()) {
        return false;
      } else {
        // 将栈顶的元素弹出
        stack.pop();
      }
    }
  }
  return stack.size() == 0;
}
console.log(is_leagl_brackets("()()))"));
console.log(is_leagl_brackets("sdf(ds(ew(we)rw)rwqq)qwewe"));
console.log(is_leagl_brackets("()()sd()(sd()fw))("));

逆波兰表达式（后缀表达式）

#编写函数，实现逆波兰表达式，也就是将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。
#等价于 (4 + (13 / 5)) = 6
["4", "13", "5", "/", "+"]
#等价于 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]

实例代码

var stack = new Stack();
for (var i = 0; i < exp.length; i++) {
  var item = exp[i];
  if (["+", "-", "*", "/"].indexOf(item) >= 0) {
    // 从栈顶弹出两个元素
    var value_1 = stack.pop();
    var value_2 = stack.pop();
    // 拼成表达式
    var exp_str = value_2 + item + value_1;
    // 计算并取整
    var res = parseInt(eval(exp_str));
    // 将计算结果压如栈
    stack.push(res.toString());
  } else {
    stack.push(item);
  }
}
// 表达式如果是正确的,最终,栈⾥还有⼀个元素,且正是表达式的计算结果
return stack.pop();
};
var exp_1 = ["4", "13", "5", "/", "+"];
var exp_2 = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"];
console.log(calc_exp(exp_1));
console.log(calc_exp(exp_2));

线性表-栈

# 栈的实现

# 栈的应用

栈的实现

栈的应用