前言——什么是数据结构？

经常听到别人讨论数据结构和算法，但对于它具体是什么，可能大部分初学阶段的人还是会云里雾里

虽然大家在大学时期上过一门叫数据结构的课程，但是大学老师一般都是只讲思想，并没有实际操作，而且在学习时也感觉比较难，考完试就忘得差不多了，所以，自己打算使用JavaScript再重温一遍

那么，回到小标题，数据结构是什么？这里引用百度百科的一句话：

• 数据结构就是在计算机中，存储和组织数据的方式

那么话不多说，直接开始进行学习吧！

栈

• 我们知到数组是一种线性结构，并且可以在任意位置进行插入和删除数据
• 但是有的时候，为了实现某些功能，需要对这种任意性加以限制
• 而栈和队列，就是比较常见的受限的线性结构
• 栈是一种很常见的数据结构，不管实在生活中还是在计算机应用中都非常的广泛

栈结构示意图

1. 进栈操作
2. 出栈操作

栈的特点

• 只允许在一端进行插入和删除运算，这端被称为栈顶，另一端称为栈底
• 向栈插入新的元素称为进栈、入栈或压栈，他是把新元素放到栈顶元素的上面，使之称为新的栈顶元素
• 从一个栈删除元素又称为出栈、退栈或弹栈，它是把栈顶元素删除，并是相邻的元素成为新的栈顶元素
• 一句话就可以描述栈的特性：后进先出

栈结构的实现

• 实现栈结构有两种比较常见的方式

1. 基于数组的实现
2. 基于链表的实现

• 栈的部分常见操作

1. push(element):为栈顶添加一个新元素
2. pop():移除并返回栈顶元素
3. peek()查看栈顶元素，不对栈做任何修改
4. isEmpty():判断栈是否为空，为空返回true，不为空则返回false
5. size():返回栈的元素个数，和length很像
6. toString():将栈的内容以字符串返回

在这里，我使用数组结构来实现

// 封装栈
function Stack() {
    // 栈的属性
    this.item = [];
    //栈的操作
    // 1.将元素压入栈
    Stack.prototype.push = function(element) {
            this.item.push(element)
        }
    // 2.从栈中取出元素
    Stack.prototype.pop = function() {
            if (this.isEmpty()) { // 先判断栈是否为空
                console.log('栈为空');
                return null;
            }
            return this.item.pop();
        }
    // 3.查看栈顶元素
    Stack.prototype.peek = function() {
            if (this.isEmpty()) { // 先判断栈是否为空
                console.log('栈为空');
                return null;
            }
            return this.item[this.item.length - 1]
        }
    // 4.判断栈是否为空
    Stack.prototype.isEmpty = function() {
            if (this.item.length <= 0) {
                return true;
            }
            return false;
        }
    // 5. 获取栈中元素的个数
    Stack.prototype.size = function() {
        return this.item.length;
    }

    // 6.toString方法
    Stack.prototype.toString = function() {
        var resultString = '';
        for (var i of this.item) {
            resultString += i;
        }
        return resultString;
    }
}
//栈的使用

var s = new Stack()
s.push(2);
s.push(4);
s.push(6);
console.log(s.size()); //输出3
console.log(s.toString()); //输出246
s.pop();
console.log(s.peek()); //输出4
console.log(s.toString()); //输出24

实际问题应用

正十进制整数转二进制 采用除2反向取余的方法，相信大家也不陌生

这里以十进制数28转换过程为例，而反向取余的过程，就可以使用栈来实现

//函数：将十进制正整数转换成二进制
function dec2bin(num) {
    //定义栈对象
    var s = new Stack();
    while (num > 0) { //当num大于0时，则还可以继续做运算
        s.push(num % 2); //将num除2的余数存入栈中
        num = Math.floor(num / 2); //注意，这里除2要向下取整
    }
    console.log(s.toString());
    //从栈中取出0、1
    var binaryString = '';
    while (!s.isEmpty()) {
        binaryString += s.pop();
    }
    return binaryString;
}
var binary = dec2bin(28);
console.log(binary); //输出11100

未完待续。。。

下节预告，队列