数据结构与算法(1) - 栈

前言：为什么要学习数据结构

编程语言是相通的
人们常说，编程语言是相通的，学会了一门，其他语言也可以很轻松的掌握，我认为这是一个似是而非的说法。
每一门编程语言都离不开变量，条件判断，循环这些概念，但是每门编程语言又有自己的使用范围，都有自己所擅长的领域。即便nodejs已经可以一统前后端，也总有他不能胜任的工作
多年的工作经验告诉我，相通的不是语言，而是数据结构与算法
学习数据结构的目标

提高算法能力
提高程序框架设计能力
供你面试装逼(这点真的没毛病，尤其是前端面试)

学习数据结构需要的知识储备
我觉得你需要非常熟练的使用数组这个数据类型，再一个去知道如何在js中定义一个类。这里推荐下阮一峰老师的一篇文章Javascript定义类的三种方法。接下来我将以我粗浅的认识与大家一起学习数据结构与算法

数据结构之 -- 栈

1. 栈的定义

栈是一种特殊的线性表，仅能够在栈顶进行操作，有先进后出（后进先出）的特点

栈.png

这里可以给大家聚一下生活中的例子，对大家对栈的理解有很大的帮助。玩羽毛球的同学有时会买一桶羽毛球，而这个羽毛球桶就是典型的栈结构

羽毛球.jpeg

2. 栈的实现

2.1 数据存储

从数据存储的角度看，要实现栈有两种方式，一种是以数组做基础，一种是以链表为基础。数组是最简单的实现方式，链表在后面会作为单独的一种数据结构来讲解
我们先来定一个一个简单的Stack类

function Stack() {
  var items = []; // 使用数组存储数据
}

2.2 栈的方法

栈有以下几个方法

push 添加一个元素到栈顶(向桶里放入一个羽毛球)
pop 弹出栈顶元素(从桶里拿出一个羽毛球)
top 返回栈顶还俗，注意，不是弹出(看一眼不拿)
isEmpty 判断栈是否为空
size 返回栈内元素的个数
clear 清空栈
接下来，我们逐一实现这些方法

2.2.1 push方法

// push方法向栈里压入一个元素
this.push = function(item) {
  items.push(item)
}

2.2.2 pop方法

// pop方法把栈顶元素弹出
this.pop = function() {
  return items.pop()
}

2.2.3 top方法

// top方法返回栈顶元素
this.top = function() {
  return items[items.length - 1]
}

2.2.4 isEmpty方法

// isEmpty方法判断栈是否为空
this.isEmpty = function() {
  return items.length == 0;
}

2.2.5 size方法

// size方法返回栈内元素的个数
this.size = function() {
  return items.length
}

2.2.6 clear方法

// clear方法清空栈
this.clear = function() {
  items = []
}

最终完整版如下

function Stack() {
    var items = [];  // 使用数组存储数据

    // push方法向栈里压入一个元素
    this.push = function(item){
        items.push(item);
    };

    // pop方法把栈顶的元素弹出
    this.pop = function(){
        return items.pop();
    };

    // top 方法返回栈顶元素
    this.top = function(){
        return items[items.length - 1];
    };

    // isEmpty返回栈是否为空
    this.isEmpty = function(){
        return items.length == 0;
    };

    // size方法返回栈的大小
    this.size = function(){
        return items.length;
    };

    // clear 清空栈
    this.clear = function(){
        items = []
    }
}

2.3 被欺骗的感觉

看完上面的实现，很多同学会说，佑弟你骗我，说的那么神乎其神的数据结构，这里的栈竟然就是对数组进行了一层封装而已啊！WTF
真的是只做了一层封装吗？请大家思考以下问题

给你一个数组，你可以通过索引操作任意元素，但是给你一个栈，你能操作栈内任意元素吗，栈提供的方法只允许我们操作栈顶元素，也就是数组的最后一个元素，这种限制其实提供给我们一种思考问题的方式，这个方式也就是栈的特性，后进先出。
既然实现栈用的是数组，那栈能做的事情，数组也一样可以做，为什么要多此一举弄个栈出来？封装是为了隐藏实现细节，有时候站在栈的角度思考问题比站在数组的角度思考问题更加方便，后面的练习你就会有所体会

3. 栈的应用练习

在这里我们通过一个练习题，你就能明白我刚才所说的站在栈的肩膀上思考问题有时候比站在数组的肩膀上思考问题更加方便

3.1 括号的合法

3.1.1 题目要求

下面的字符串中包含小括号，请便携一个函数判断字符串中的括号是否合法，所谓的合法就是括号是成对出现

((ab(cd)g(aa))(cc))   合法
(ab(cd))(bbdsf)(1    不合法

3.1.2 思路分析

括号存在嵌套关系，也存在并列关系，如果使用数组存储这些括号，再想办法一一匹配左右括号似乎是一个可行的办法，可是如何判断一个左括号对应的是哪个右括号呢？
现在，我们站在栈的肩膀上去思考这个问题，解题的过程就非常简单了，我们可以遍历这个字符串，对每个字符做以下操作

遇到左括号，就把左括号压入栈顶
遇到右括号，判断栈是否为空，为空则说明没有与之对应的左括号，不合法，如果不为空，则将栈顶元素弹出，这对括号就抵消了
当for循环结束后，如果栈为空，则说明左右括号全部抵消，则合法，反之不合法

3.1.3 示例代码

function isLegitimate(string){
    var stack = new Stack();
    for(var i=0; i<string.length; i++ ){
        var item = string[i];
        if(item == "("){
            // 将左括号压入栈
            stack.push(item);
        }else if (item==")"){
            // 如果为空,就说明没有左括号与之抵消
            if(stack.isEmpty()){
                return false;
            }else{
                // 将栈顶的元素弹出
                stack.pop();
            }
        }

    }
    return stack.size() == 0;
};
console.log(isLegitimate("((ab(cd)g(aa))(cc))"))
console.log(isLegitimate("(ab(cd))(bbdsf)(1"))

3.1.4 小结

栈的底层是不是使用了数组不重要，重要的是栈的后进先出的特性，重要的是你只能操作栈顶元素，一定要忽略底层如何实现，去关心栈的特性。
在我们写代码的时候，经常进行回退的操作，control+z就可以了，那你有没有想过，这个就可以用栈来实现，每一步都放到栈中，当你想回退的时候，将栈顶元素弹出，你就得到了你之前一步的操作

数据结构与算法(1) - 栈