数据驱动型的设计04之Stack
- 2019 年 10 月 7 日
- 筆記
先跟大家分享在mixlab社区某成员抛出的一个非常有意思的例子：
“
一个哥们，有次聚会说自己买了很多条iphone数据线，家里每个房间插一条，走到哪儿都能随时充电。在场的姑娘们都当成是段子笑笑就过去了，只有个细心的姑娘悄悄问他买了多少条，他说42条。现在他和她在北京三环内共有42个房间的数套豪宅愉快地生活，下个月结婚。这就是数据分析。
”
形象生动地描述了数据分析的应用场景。回到主题，本系列从数据结构相关的计算机知识出发，希望从数据的角度提出一些数据驱动的设计思维模式。
总体介绍数据结构与设计的关系，用数据结构的方式来思考设计，并通过几个案例介绍一些大的思路。
介绍数据结构中的链表结构，并探讨设计中可能的链表数据。
介绍数据结构中的队列结构，及在智能设计中的应用。
以下为本期正文内容：
Stack
堆栈
是一个后进先出(LIFO)的数据类型：最后一个放入堆栈中的物体总是被最先拿出来。读者还记得上一期Queue队列的先进先出（FIFO）模式吗？
堆栈中定义两个最重要的操作是push和pop。
push操作在堆栈的顶部加入一个元素。
pop操作相反， 在堆栈顶部移去一个元素， 并将堆栈的大小减一。
同样的，Stack可以基于上期实现的LinkedList结构，来实现。
class LinkedList{...}; class Stack{ constructor() { this.linkedList = new LinkedList(); } push(value) { this.linkedList.prepend(value); } pop() { const removedTail = this.linkedList.deleteHead(); return removedTail ? removedTail.value : null; }}
栈的应用
编写一个程序，判断括号是否匹配。比如下面这些字符串：
(()()()()) (((()))) (()((())()))((((((()) ())) (()()(()
我们先给Stack增加一个方法，用于判断是否为空：
Stack.prototype.isEmpty=function() { return !this.linkedList.tail; }
图示来理解下过程：
1
用一个栈来存放所有的“（ ”，遍历字符串的每一位，判断是否“（ ”，若为“（ ”，则放入栈中
2
若是“ ）”，则出栈
3
遍历完后，判断下栈是否为空，若为空，则此字符串的括号是匹配的。
代码如下：
function checker(symbolStr){ var s = new Stack(); var balanced = true; var index = 0; for(var i=0;i<symbolStr.length;i++){ if(balanced){ var symbol = symbolStr[index]; if(symbol=='('){ s.push(symbol); }else{ if(s.isEmpty()){ balanced = false; }else{ s.pop(); }; }; index = index + 1; };}; if (balanced && s.isEmpty()){ return true } else{ return false }; };
以上是关于Stack“后进先出”模式具体应用的一个小练习。
补充一个，堆栈的形态在UI的应用。IOS的应用管理，把每个程序用卡片的形式作隐喻，在多任务的操作中配合手势区域的交互手势，让多任务操作非常便捷。
待续。
