Author | 王平安 |
---|---|
pingan8787@qq.com | |
博 客 | www.pingan8787.com |
微 信 | pingan8787 |
每日文章推荐 | https://github.com/pingan8787/Leo_Reading/issues |
微信公众号 | 前端自习课 |
最近公司内部在开始做前端技术的技术分享,每周一个主题的 每周一练,以基础知识为主,感觉挺棒的,跟着团队的大佬们学习和复习一些知识,新人也可以多学习一些知识,也把团队内部学习氛围营造起来。
我接下来会开始把每周一练的题目和知识整理一下,便于思考和巩固,就像今天这篇开始。
学习的道路,很漫长,要坚持,希望大家都能掌握自己喜欢的技术,和自己需要的技术。
本周练习内容:数据结构与算法 —— Stack
这些都是数据结构与算法,一部分方法是团队其他成员实现的,一部分我自己做的,有什么其他实现方法或错误,欢迎各位大佬指点,感谢。
一、栈有什么特点,生活中有什么例子?
- 栈( stack )又称堆栈,是一种后进先出的有序集合,其中一端为栈顶,另一端为栈底,添加元素(称为压栈/入栈或进栈)时,将新元素压入栈顶,删除元素(称为出栈或退栈)时,将栈底元素删除并返回被删除元素。
- 特点:先进后出,后进先出。
- 例子:一叠书、一叠盘子。
二、实现一个栈,并实现下面方法
push(element)
:添加一个新元素到栈顶。pop()
:移除栈顶的元素,同时返回被移除的元素。peek()
:返回栈顶的元素,不对栈做任何修改 (这个方法不会移除栈顶的元素,仅仅返回它)。isEmpty()
:如果栈没有任何元素就返回true
,否则返回false
。clear()
:移除栈里面的所有元素。size()
:返回栈里的元素个数。这个方法与数组的length
属性类似。
方法1:ES6实现
1 | class Stack { |
上面实现的方式虽然简单,但是内部 items
属性是公共的,为了满足面向对象变成私有性的原则,我们应该让 items
作为私有属性,因此我们可以使用 ES6 中 Symbol
或 WeakMap
来实现:
方法2:使用 ES6 的 Symbol 基本数据类型实现
知识点复习:ES6 中的 Symbol 介绍
1 | const _items = Symbol() |
方法3:使用 ES6 的 WeakMap 实现
知识点复习:ES6 中的 WeakMap 介绍
1 | const items = new WeakMap() |
三、编写一个函数,实现十进制转二进制
题目意思很简单,就是十进制转二进制,但是在实际工作开发中,我们更愿意实现的是任意进制转任意进制,不过呢,我们还是以解决问题为首要目标呀。
当然,业务需求可以直接使用 toString(2)
方法,但是为了练习,咱还是不这么用咯。
方法1:使用前面定义的 Stack 类
这里使用前面题目中定义的 Stack
类。
1 | /** |
方法2:简单实现
下面这个方法,其实不太好,因为没有怎么用到这次要练习的栈方法,哈哈。
1 | /** |
另外可以参考:wikiHow - 从十进制转换为二进制。
四、编写一个函数,实现检验圆括号顺序的有效性
主要目的就是:该函数接收一个圆括号字符串,判断里面的括号顺序是否有效,如果有效则返回 true
反之 false
。
如:
(
->false
()
->true
(()
->false
())
->false
())
->false
(((()()))())
->true
这个题目实现的主要方法是:遍历字符串,先排除错误情况,然后将 (
入栈保存,将 )
入栈匹配前一个元素是否是 (
,如果是,则 pop()
前一个元素 (
,如果不是,则 push()
这个 )
入栈,最终查看栈是否为空,若是则检验成功,否则失败。
方法1:使用前面定义的 Stack 类
这里使用前面题目中定义的 Stack
类。
1 | /** |
方法2:出入栈操作
1 | /** |
五、改造题二,添加一个 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 |
使用示例如下:
1 | let stack = new Stack(); |
提示:利用辅助栈(Web 端可利用数组),每次对栈 push/pop 元素时,也同时更新辅助栈(存储最小元素的位置)
方法1:小操作
1 | class Stack { |
方法2:与方法1中push实现的差异
1 | class Stack { |
下周预告
下周将练习队列(Queue) 的题目,开始翻起算法书籍学习咯。