首页 > 其他 > 详细

数据结构-栈

时间:2021-03-14 00:05:52      阅读:20      评论:0      收藏:0      [点我收藏+]

1.概念

  是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

生活中基于栈的经验有:托盘,邮件消息等。具体图解如下图所示。

技术分享图片

 

 2.自定义栈的完整操作

// 栈类
function Stack() {
  // 栈中的属性
  var items = [];

  // 栈相关的方法
  // 压栈操作
  this.push = function (element) {
    items.push(element);
  };

  // 出栈操作
  this.pop = function () {
    return items.pop();
  };

  // peek操作
  this.peek = function () {
    return items[items.length - 1];
  };

  // 判断栈中的元素是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  // 获取栈中元素的个数
  this.size = function () {
    return items.length;
  };
}

3.使用栈来实现十进制转二进制

// 封装十进制转二进制的函数
function dec2bin(decNumer) {
  // 定义变量
  var stack = new Stack();
  var remainder;
  // 循环除法
  while (decNumer > 0) {
    remainder = decNumer % 2;
    decNumer = Math.floor(decNumer / 2);
    stack.push(remainder);
  }
  // 将数据取出
  var binayrString = "";
  while (!stack.isEmpty()) {
    binayrString += stack.pop();
  }
  return binayrString;
}

4.判断一个序列是否为合理的出栈顺序

// pushV是入栈顺序的数组,popV是要判断的出栈顺序数组
function IsPopOrder(pushV, popV) {
  const stack = [];
  pushV.forEach(item => {
    if (item === popV[0]) {
      popV.shift();
      while(stack.length && stack[stack.length - 1] === popV[0]) {
        stack.pop();
        popV.shift();
      }
    } else {
      stack.push(item);
    }
  })
  return !stack.length && !popV.length;
}

数据结构-栈

原文:https://www.cnblogs.com/zjqzilq/p/14529396.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!