伏龙阁资源网

每周一练 之 数据结构与算法（Stack）
站长资源 2024/11/27 佚名
2 0

最近公司内部在开始做前端技术的技术分享，每周一个主题的 每周一练，以基础知识为主，感觉挺棒的，跟着团队的大佬们学习和复习一些知识，新人也可以多学习一些知识，也把团队内部学习氛围营造起来。

我接下来会开始把每周一练的题目和知识整理一下，便于思考和巩固，就像今天这篇开始。

学习的道路，很漫长，要坚持，希望大家都能掌握自己喜欢的技术，和自己需要的技术。

本周练习内容：数据结构与算法 —— Stack

这些都是数据结构与算法，一部分方法是团队其他成员实现的，一部分我自己做的，有什么其他实现方法或错误，欢迎各位大佬指点，感谢。

一、栈有什么特点，生活中有什么例子"text-align: center"> 每周一练 之 数据结构与算法（Stack）

二、实现一个栈，并实现下面方法

  1. push(element)：添加一个新元素到栈顶。
  2. pop()：移除栈顶的元素，同时返回被移除的元素。
  3. peek()：返回栈顶的元素，不对栈做任何修改 (这个方法不会移除栈顶的元素，仅仅返回它)。
  4. isEmpty()：如果栈没有任何元素就返回 true，否则返回 false。
  5. clear()：移除栈里面的所有元素。
  6. size()：返回栈里的元素个数。这个方法与数组的 length 属性类似。

方法1：ES6实现

class Stack {
  constructor (){
    this.items = []
  }
  push( element ){
    this.items.push(element)
  }
  pop(){
    return this.items.pop()
  }
  peek(){
    return this.items[this.items.length - 1]
  }
  isEmpty(){
    return this.items.length === 0
  }
  clear(){
    this.items = []
  }
  size(){
    return this.items.length
  }
}

上面实现的方式虽然简单，但是内部 items 属性是公共的，为了满足面向对象变成私有性的原则，我们应该让 items 作为私有属性，因此我们可以使用 ES6 中 Symbol 或 WeakMap 来实现：

方法2：使用 ES6 的 Symbol 基本数据类型实现
知识点复习：ES6 中的 Symbol 介绍

const _items = Symbol()
class Stack {
  constructor (){
    this[_items] = []
  }
  push (element){
    this[_items].push(element)
  }
  // 剩下方法和第一种实现的差不多，这里省略
  // 只要把前面方法中的 this.items 更改为 this[_items]
}

 方法3：使用 ES6 的 WeakMap 实现

知识点复习：ES6 中的 WeakMap 介绍

 

const items = new WeakMap()
class Stack {
  constructor (){
    items.set(this, [])
  }
  push (element){
    let item = items.get(this)
    item.push(element)
  }
  // 剩下方法和第一种实现的差不多，这里省略
  // 只要把前面方法中的获取 this.items 的方式，更改为 items.get(this) 获取
}

 三、编写一个函数，实现十进制转二进制

题目意思很简单，就是十进制转二进制，但是在实际工作开发中，我们更愿意实现的是任意进制转任意进制，不过呢，我们还是以解决问题为首要目标呀。

当然，业务需求可以直接使用 toString(2) 方法，但是为了练习，咱还是不这么用咯。

方法1：使用前面定义的 Stack 类

这里使用前面题目中定义的 Stack 类。

/**
 * 十进制转换为二进制
 * @param {Number} bit 
 */
function bitset (bit){
  if(bit == 0) return '0'
  if(!/^[0-9]+."htmlcode">



/**
 * 十进制转换为二进制
 * @param {Number} bit 
 */
function bitset (bit){
  if(bit == 0) return '0'
  if(!/^[0-9]+."https://zh.wikihow.com/%E4%BB%8E%E5%8D%81%E8%BF%9B%E5%88%B6%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E8%BF%9B%E5%88%B6">wikiHow - 从十进制转换为二进制。


四、编写一个函数，实现检验圆括号顺序的有效性


主要目的就是：该函数接收一个圆括号字符串，判断里面的括号顺序是否有效，如果有效则返回 true 反之 false。

如：


    
  
  1. (   -> false
    2. 
  
  2. ()  -> true
    3. 
  
  3. (() -> false
    4. 
  
  4. ()) -> false
    5. 
  
  5. ()) -> false
    6. 
  
  6. (((()()))()) -> true
    7. 



这个题目实现的主要方法是：遍历字符串，先排除错误情况，然后将 ( 入栈保存，将 ) 入栈匹配前一个元素是否是 ( ，如果是，则 pop() 前一个元素 (，如果不是，则 push() 这个 ) 入栈，最终查看栈是否为空，若是则检验成功，否则失败。




方法1：使用前面定义的 Stack 类


这里使用前面题目中定义的 Stack 类。





/**
 * 检验圆括号顺序的有效性
 * @param {String} str 
 */
function validParentheses (str){
  if(!str || str.length === 0 || str[0] === ')') return false

  let stack = new Stack()
  str.split('').forEach(char => {
    let status = stack.peek() === '(' && char === ')'
    status "htmlcode">



/**
 * 检验圆括号顺序的有效性
 * @param {String} str 
 */
function validParentheses (str){
  if(!str || str.length === 0 || str[0] === ')') return false

  let arr = []
  for(let i = 0; i < str.length ; i++){
    str[i] === '(' "color: #ff0000">五、改造题二，添加一个 min 函数来获得栈中最小元素




  
    
      步骤
      数据栈
      辅助栈
      最小值
    
  
  
    
      1.push 3
      3
      0
      3
    
    
      2.push 4
      3, 4
      0, 0
      3
    
    
      3.push 2
      3, 4, 2
      0, 0, 2
      2
    
    
      4.push 1
      3, 4, 2 ,1
      0, 0, 2, 3
      1
    
    
      5.pop
      3, 4, 2
      0, 0, 2
      2
    
    
      6.pop
      3, 4
      0, 0
      3
    
    
      7.push
      3, 4 ,0
      0, 0, 2
      0
    
  




使用示例如下：





let stack = new Stack();
stack.push(3);
console.log('After push 3, Min item is', stack.min());
stack.push(4);
console.log('After push 4, Min item is', stack.min());
stack.push(2);
console.log('After push 2, Min item is', stack.min());
stack.push(1);
console.log('After push 1, Min item is', stack.min());
stack.pop();
console.log('After pop, Min item is', stack.min());
stack.pop();
console.log('After pop, Min item is', stack.min());
stack.push(0);
console.log('After push 0, Min item is', stack.min());






提示：利用辅助栈（Web 端可利用数组），每次对栈 push/pop 元素时，也同时更新辅助栈（存储最小元素的位置）


方法1：小操作





class Stack {
 constructor() {
  this.items = [];
  this.minIndexStack = [];
 }

 push(element) {
  this.items.push(element);
  let minLen = this.minIndexStack.length;
  let minItemIndex = this.minIndexStack[minLen - 1];
  if(minLen === 0 || this.items[minItemIndex] > item) {
   this.minIndexStack.push(this.items.length - 1);
  } else {
   this.minIndexStack.push(minItemIndex);
  }
 }

 pop() {
  this.minIndexStack.pop();
  return this.items.pop();
 }
 
 min() {
  let len = this.minIndexStack.length;
  return (len > 0 && this.items[this.minIndexStack[len - 1]]) || 0;
 }

 peek() {
  return this.items[this.items.length - 1];
 }
 
 // 省略其它方法
}







方法2：与方法1中push实现的差异





class Stack {
  constructor (){
    this.items = [] // 数据栈
    this.arr = []  // 辅助栈
  }
  push( element ){
    this.items.push(element)
    let min = Math.min(...this.items)
    this.arr.push( min === element ? this.size() - 1 : 0)
  }
  pop(){
    this.arr.pop()
    return this.items.pop()
  }
  peek(){
    return this.items[this.items.length - 1]
  }
  isEmpty(){
    return this.items.length === 1
  }
  clear(){
    this.items = []
  }
  size(){
    return this.items.length
  }
  min (){
    let last = this.arr[this.arr.length - 1]
    return this.items[last]
  }
}







以上所述是小编给大家介绍的数据结构与算法（Stack）详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
www.wwsws.com 伏龙阁资源网
39,976影音资源
44,792技术资源
21,817软件资源
651,128站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接