数据驱动型的设计04之Stack

mixlab

发布于 2019-09-26 15:09:58

4540

发布于 2019-09-26 15:09:58

先跟大家分享在mixlab社区某成员抛出的一个非常有意思的例子：

“

一个哥们，有次聚会说自己买了很多条iphone数据线，家里每个房间插一条，走到哪儿都能随时充电。在场的姑娘们都当成是段子笑笑就过去了，只有个细心的姑娘悄悄问他买了多少条，他说42条。现在他和她在北京三环内共有42个房间的数套豪宅愉快地生活，下个月结婚。这就是数据分析。

”

形象生动地描述了数据分析的应用场景。回到主题，本系列从数据结构相关的计算机知识出发，希望从数据的角度提出一些数据驱动的设计思维模式。

第01期

总体介绍数据结构与设计的关系，用数据结构的方式来思考设计，并通过几个案例介绍一些大的思路。

第02期

介绍数据结构中的链表结构，并探讨设计中可能的链表数据。

第03期

介绍数据结构中的队列结构，及在智能设计中的应用。

以下为本期正文内容：

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;
 }

图示来理解下过程：

用一个栈来存放所有的“（ ”，遍历字符串的每一位，判断是否“（ ”，若为“（ ”，则放入栈中

若是“ ）”，则出栈

遍历完后，判断下栈是否为空，若为空，则此字符串的括号是匹配的。

代码如下：

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的应用管理，把每个程序用卡片的形式作隐喻，在多任务的操作中配合手势区域的交互手势，让多任务操作非常便捷。