數(shù)據(jù)結(jié)構(gòu)淺析：棧

每一位想在大型技術(shù)公司申請職位的開發(fā)者，如果花了數(shù)天時間練習(xí)常見算法面試題都會說：

“哇。我真的覺得數(shù)據(jù)結(jié)構(gòu)很難”

數(shù)據(jù)結(jié)構(gòu)是什么？為什么它們?nèi)绱酥匾?？維基百科給出了簡明而準(zhǔn)確的答案：

數(shù)據(jù)結(jié)構(gòu)是在計算機(jī)為了組織數(shù)據(jù)的特定方式，目的是為了高效地使用數(shù)據(jù)。

注意這里的關(guān)鍵詞是高效，一個在分析不同的數(shù)據(jù)結(jié)構(gòu)時你會常常聽說的詞語。

這些數(shù)據(jù)結(jié)構(gòu)提供不同的方式來存儲數(shù)據(jù)，以便快速、動態(tài)地搜索、插入、移除、更新數(shù)據(jù)。

盡管和計算機(jī)一樣強(qiáng)大，它們?nèi)匀恍枰噶畈拍芡瓿扇魏斡幸饬x的任務(wù)（至少在人工智能出來之前是這樣）。在此之前你必須給它們盡可能明確、高效的指令。

如同你可以使用50種不同的方式來建造房子一樣，你也可以使用50種不同方式來組織數(shù)據(jù)。幸運(yùn)的是，很多聰明的人已經(jīng)構(gòu)建很多偉大的經(jīng)過時間考驗(yàn)的數(shù)據(jù)結(jié)構(gòu)。你所要做的就是學(xué)習(xí)它們是什么，它們?nèi)绾喂ぷ?，以及怎樣最好的使用它們。下面是一些最常用的?shù)據(jù)結(jié)構(gòu)列表。我將在后續(xù)文章中逐一介紹它們--本文先介紹棧。盡管它們常常有共同之處，但是為了適用于特定的場景，這些數(shù)據(jù)結(jié)構(gòu)中每一個都有一些細(xì)微差別：

• 棧（Stacks）
• 隊(duì)列（Queues）
• 鏈表（Linked Lists）
• 集合（Sets）
• 樹（Trees）
• 圖（Graphs）
• 哈希表（Hash Tables）

你會遇到這些數(shù)據(jù)結(jié)構(gòu)變體，如雙向鏈表，B-樹以及優(yōu)先隊(duì)列。但是一旦你理解了這些核心的實(shí)現(xiàn)，要理解這些變體就會很簡單。

所以就從分析棧開始我們的數(shù)據(jù)結(jié)構(gòu)之旅的第一部分。

棧

• 字面意思就是一堆數(shù)據(jù)（就像一堆煎餅）
• 添加（push）--總是添加到棧頂
• 移除（pop）--總是從棧頂開始移除
• 模式類型：先進(jìn)后出（LIFO）

• 使用范例：使用瀏覽器中的后退和前進(jìn)按鈕

在許多編程語言中，數(shù)組內(nèi)建了棧的功能。但是為了理解透徹，你將使用一個 JavaScript 對象來重新實(shí)現(xiàn)一個棧。

首先你需要創(chuàng)建一個棧用于存儲你訪問過的每一個站點(diǎn)，并且在你的棧中創(chuàng)建一個方法用于跟蹤你當(dāng)前的位置：

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

注意變量名稱前的下劃線告訴其他開發(fā)者這些變量是私有的，只能通過該類的方法操作，不能外部直接操作。例如，我不能執(zhí)行這樣的代碼：

browserHistory._position = 2.

這就是為什么為我要創(chuàng)建 top() 方法用于返回棧的當(dāng)前位置。

在本例中，你訪問的每一個網(wǎng)站都將被存放到你的瀏覽器歷史棧中。為了幫助你跟蹤它在棧中的位置，你可以用每一個站點(diǎn)的位置作為關(guān)鍵字，然后每添加一個站點(diǎn)，位置就遞增。在這里我通過 push 方法實(shí)現(xiàn)：

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

上面的代碼執(zhí)行以后，storage 對象將是這樣的：

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

所有想象一下，你現(xiàn)在瀏覽 Netflix，但是因?yàn)樵?Free Code Camp 上還有一個困難的遞歸問題沒有完成而愧疚。你決定點(diǎn)擊返回按鈕，回去解決它。

這一行為在你的棧中是怎么表現(xiàn)的的？使用 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

通過點(diǎn)擊返回按鈕，將最近添加到瀏覽器歷史的站點(diǎn)移除，并瀏覽當(dāng)前處于棧頂?shù)恼军c(diǎn)。你同時遞減了 position 變量，所以你可以準(zhǔn)確地表示出你當(dāng)前處于瀏覽歷史的什么位置。當(dāng)然這一切都只有你的棧非空時才會發(fā)生。

到目前為止看起來都還不錯，但是被移除的對象呢？

當(dāng)你解決完問題時，決定獎賞自己回去繼續(xù)瀏覽 Netflix，點(diǎn)擊前進(jìn)按鈕就可以。但是你的棧里有 Netflix 嗎？為了節(jié)省空間你已經(jīng)將它刪除了，在你的瀏覽器歷史中再也沒有這個站點(diǎn)。

幸運(yùn)的是，pop 函數(shù)將它返回了，所以也許你可以在別的地方將它存起來以備后用。用另一個棧存起來怎么樣！

你可以創(chuàng)建一個 “forward” 棧用于存儲每一個從瀏覽器歷史中移除的站點(diǎn)。所以當(dāng)你想再次瀏覽的時候，只需要將它們從 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

你已經(jīng)使用一種數(shù)據(jù)結(jié)構(gòu)重新實(shí)現(xiàn)了瀏覽器基本的前進(jìn)、后退導(dǎo)航！

為了理解透徹，我們假設(shè)你從 Free Code Camp 網(wǎng)站進(jìn)入以一個全新的站點(diǎn)，比如 LeetCode 去做更多的練習(xí)。技術(shù)實(shí)現(xiàn)上 Netflix 仍然位于你的 forward 棧，這是沒有意義的。

幸運(yùn)的是，你可以實(shí)現(xiàn)一個簡單的 while 循環(huán)來快速去除 Netflix 以及其他站點(diǎn)：

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

非常棒！現(xiàn)在你的導(dǎo)航可以按照預(yù)期的方式工作。

快速總結(jié)一下。棧：

• 1、遵循 后進(jìn)先出（LIFO ）規(guī)則
• 2、有用于管理?xiàng)?nèi)內(nèi)容的 push（add） 和 pop（remove） 方法
• 3、有一個 top 屬性用于跟蹤棧的大小以及當(dāng)前棧頂位置
  在這一系列文章中，每一篇末尾我會對每一種數(shù)據(jù)結(jié)構(gòu)的方法做一個簡單的時間復(fù)雜度分析。

再來看一下代碼：

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)。因?yàn)槟憧偸侵喇?dāng)前位置，你不需要通過遍歷來完成項(xiàng)目的添加。

Pop(刪除)：O(1)。同樣不需要遍歷就可以移除，因?yàn)槟憧偸侵喇?dāng)前棧頂?shù)奈恢谩?/p>

Top：O(1)。當(dāng)前位置總是已知的。

棧本身沒有搜索方法，但是如果你想添加一個，你想一下時間復(fù)雜度應(yīng)該是什么？

Find(查找) 應(yīng)該是 O(n)。技術(shù)上你必須遍歷存儲的內(nèi)容知道找到你查找的內(nèi)容。這就是數(shù)組的 indexOf 方法的本質(zhì)。

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