前端也要懂的数据结构(1)--栈

图片来自网络

数据结构是开发人员的基础知识，前端开发人员也要对各种数据有了解。相信理解的越深入，越能发现他的强大。今天先和大家介绍一下最简单的数据结构栈。

1.栈的定义

栈是一种遵循后进先出原则的有序集合。先进入栈的元素在底部，后进入栈的元素在顶部。后进栈的元素先被取出，早进栈的元素后被取出。

是不是有点蒙圈了，别着急。你可以想像栈是一个水杯，先倒进去的水会在水杯的底部，后倒进去的水在水杯的顶部。如果想把水倒出来，那在水杯顶部的水会先被倒出来，底部的水要等上层的水离开之后才能被倒出来。

图片来自全景网

把栈想象成摞起来的书也能帮助你理解栈的结构。

图片来自网络

2.手动实现一个栈

已经知道了栈的定义和特性，我们可以借助数组来实现一个栈。它要符合栈的特性“后进先出”，要能够入栈和出栈。

第一步：实现入栈
JavaScript的数组添加元素又两种方式：push 和 unshift。push是添加到数组的尾部及最后一个元素的后面，而unshift则是添加到数组的头部。结合栈的特性，我们应该选择push的方式。

var stack = {
  //用数组存储元素
  items:  [], 
  //实现入栈方法 add
  add: function(element){
    stack.items.push(element);
  }
};

第二步：实现出栈
JavaScript移除元素的话有pop和shift，结合栈后进先出的特性，需要选择pop来实现元素的出栈。pop移除并返回数组的最后一个元素。

var stack = {
  //用数组存储元素
 items:  [], 
  //实现入栈方法 add
  add: function(element){
    stack.items.push(element);
  },
  //实现出栈的方法
 remove:  function(){
    return stack.items.pop();
  }
};

到这里一个最基本的栈就实现了，但是往往栈还要有其他方法。下面我们再实现一个返回栈内元素个数的方法size。

getSize: function(){
  return stack.items.length;
};

除了这些基本的方法之外，栈还可以实现很多功能。比如实现返回栈顶的元素，栈的平均数等等。

大家有空可以思考一下如何实现一个栈的方法，它能够返回栈的最小值且时间复杂度为O(1)。栈内的元素均为数字。明天晚上在下一章队列中会给出我的解法。

个人浅薄之见，欢迎大家交流指正。