数据结构浅析：栈

每一位想在大型技术公司申请职位的开发者，如果花了数天时间练习常见算法面试题都会说：

“哇。我真的觉得数据结构很难”

数据结构是什么？为什么它们如此重要？维基百科给出了简明而准确的答案：

数据结构是在计算机为了组织数据的特定方式，目的是为了高效地使用数据。

注意这里的关键词是高效，一个在分析不同的数据结构时你会常常听说的词语。

这些数据结构提供不同的方式来存储数据，以便快速、动态地搜索、插入、移除、更新数据。

尽管和计算机一样强大，它们仍然需要指令才能完成任何有意义的任务（至少在人工智能出来之前是这样）。在此之前你必须给它们尽可能明确、高效的指令。

如同你可以使用50种不同的方式来建造房子一样，你也可以使用50种不同方式来组织数据。幸运的是，很多聪明的人已经构建很多伟大的经过时间考验的数据结构。你所要做的就是学习它们是什么，它们如何工作，以及怎样最好的使用它们。下面是一些最常用的数据结构列表。我将在后续文章中逐一介绍它们--本文先介绍栈。尽管它们常常有共同之处，但是为了适用于特定的场景，这些数据结构中每一个都有一些细微差别：

• 栈（Stacks）
• 队列（Queues）
• 链表（Linked Lists）
• 集合（Sets）
• 树（Trees）
• 图（Graphs）
• 哈希表（Hash Tables）

你会遇到这些数据结构变体，如双向链表，B-树以及优先队列。但是一旦你理解了这些核心的实现，要理解这些变体就会很简单。

所以就从分析栈开始我们的数据结构之旅的第一部分。

栈

• 字面意思就是一堆数据（就像一堆煎饼）
• 添加（push）--总是添加到栈顶
• 移除（pop）--总是从栈顶开始移除
• 模式类型：先进后出（LIFO）

• 使用范例：使用浏览器中的后退和前进按钮

在许多编程语言中，数组内建了栈的功能。但是为了理解透彻，你将使用一个 JavaScript 对象来重新实现一个栈。

首先你需要创建一个栈用于存储你访问过的每一个站点，并且在你的栈中创建一个方法用于跟踪你当前的位置：

class Stack {
  constructor(){
    this._storage = {};  
    this._position = -1; // 0 indexed when we add items!
  }
  top(){
    return this._position;
  }
}
let browserHistory = new Stack();

注意变量名称前的下划线告诉其他开发者这些变量是私有的，只能通过该类的方法操作，不能外部直接操作。例如，我不能执行这样的代码：

browserHistory._position = 2.

这就是为什么为我要创建 top() 方法用于返回栈的当前位置。

在本例中，你访问的每一个网站都将被存放到你的浏览器历史栈中。为了帮助你跟踪它在栈中的位置，你可以用每一个站点的位置作为关键字，然后每添加一个站点，位置就递增。在这里我通过 push 方法实现：

class Stack {
  constructor(){
    this._storage = {}; 
    this._position = -1;
  }
  push(value){
    this._position++; 
    this._storage[this._position] = value 
  }
  top(){
    return this._position;
  }
}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to Medium
browserHistory.push("medium.com"); // navigating to Free Code Camp
browserHistory.push("freecodecamp.com"); // navigating to Netflix
browserHistory.push("netflix.com"); // current site

上面的代码执行以后，storage 对象将是这样的：

{
  0: “google.com”
  1: “medium.com”
  2: “freecodecamp.com”
  3: “netflix.com”
}

所有想象一下，你现在浏览 Netflix，但是因为在 Free Code Camp 上还有一个困难的递归问题没有完成而愧疚。你决定点击返回按钮，回去解决它。

这一行为在你的栈中是怎么表现的的？使用 pop：

class Stack {
 
  constructor(){
    this._storage = {};
    this._position = -1;
  }
 
  push(value){
    this._position++; 
    this._storage[this._position] = value; 
  }
 
  pop(){
    if(this._position > -1){
      let val = this._storage[this._position]; 
      delete this._storage[this._position]; 
      this._position--;
      return val;
    }
  }
  top(){
    return this._position;
  }
}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to Medium
browserHistory.push("medium.com"); // navigating to Free Code Camp
browserHistory.push("freecodecamp.com"); // navigating to Netflix
browserHistory.push("netflix.com"); //current site
browserHistory.pop(); //Returns netflix.com
//Free Code Camp is now our current site

通过点击返回按钮，将最近添加到浏览器历史的站点移除，并浏览当前处于栈顶的站点。你同时递减了 position 变量，所以你可以准确地表示出你当前处于浏览历史的什么位置。当然这一切都只有你的栈非空时才会发生。

到目前为止看起来都还不错，但是被移除的对象呢？

当你解决完问题时，决定奖赏自己回去继续浏览 Netflix，点击前进按钮就可以。但是你的栈里有 Netflix 吗？为了节省空间你已经将它删除了，在你的浏览器历史中再也没有这个站点。

幸运的是，pop 函数将它返回了，所以也许你可以在别的地方将它存起来以备后用。用另一个栈存起来怎么样！

你可以创建一个 “forward” 栈用于存储每一个从浏览器历史中移除的站点。所以当你想再次浏览的时候，只需要将它们从 forward 栈 弹出来就可以，并将它们重新压入浏览器历史栈：

class Stack {
 
  constructor(){
    this._storage = {};
    this._position = -1;
  }
 
  push(value){
    this._position++; 
    this._storage[this._position] = value; 
  }
 
  pop(){
    if(this._position > -1){
      let val = this._storage[this._position]; 
      delete this._storage[this._position]; 
      this._position--;
      return val;
    }
  }
top(){
    return this._position;
  }
}
let browserHistory = new Stack();
let forward = new Stack() //Our new forward stack!
browserHistory.push("google.com");
browserHistory.push("medium.com");
browserHistory.push("freecodecamp.com");
browserHistory.push("netflix.com");
//hit the back button
forward.push(browserHistory.pop()); // forward stack holds Netflix
// ...We crush the Free Code Camp problem here, then hit forward!
  browserHistory.push(forward.pop());
//Netflix is now our current site

你已经使用一种数据结构重新实现了浏览器基本的前进、后退导航！

为了理解透彻，我们假设你从 Free Code Camp 网站进入以一个全新的站点，比如 LeetCode 去做更多的练习。技术实现上 Netflix 仍然位于你的 forward 栈，这是没有意义的。

幸运的是，你可以实现一个简单的 while 循环来快速去除 Netflix 以及其他站点：

//When I manually navigate to a new site, make forward stack empty
while(forward.top() > -1){
  forward.pop();
}

非常棒！现在你的导航可以按照预期的方式工作。

快速总结一下。栈：

• 1、遵循 后进先出（LIFO ）规则
• 2、有用于管理栈内内容的 push（add） 和 pop（remove） 方法
• 3、有一个 top 属性用于跟踪栈的大小以及当前栈顶位置
  在这一系列文章中，每一篇末尾我会对每一种数据结构的方法做一个简单的时间复杂度分析。

再来看一下代码：

push(value){
   this._position++; 
   this._storage[this._position] = value; 
 }

 pop(){
   if(this._position > -1){
     let val = this._storage[this._position]; 
     delete this._storage[this._position]; 
     this._position--;
     return val;
   }
 }
 
 top(){
   return this._position;
 }

Push(添加)：O(1)。因为你总是知道当前位置，你不需要通过遍历来完成项目的添加。

Pop(删除)：O(1)。同样不需要遍历就可以移除，因为你总是知道当前栈顶的位置。

Top：O(1)。当前位置总是已知的。

栈本身没有搜索方法，但是如果你想添加一个，你想一下时间复杂度应该是什么？

Find(查找) 应该是 O(n)。技术上你必须遍历存储的内容知道找到你查找的内容。这就是数组的 indexOf 方法的本质。

本文译自：A Gentle Introduction to Data Structures: How Stacks Work