數(shù)據(jù)結(jié)構(gòu)淺析：棧
每一位想在大型技術(shù)公司申請職位的開發(fā)者酌摇，如果花了數(shù)天時間練習常見算法面試題都會說：
“哇倦始。我真的覺得數(shù)據(jù)結(jié)構(gòu)很難”
數(shù)據(jù)結(jié)構(gòu)是什么？為什么它們?nèi)绱酥匾塍希烤S基百科給出了簡明而準確的答案：
數(shù)據(jù)結(jié)構(gòu)是在計算機為了組織數(shù)據(jù)的特定方式，目的是為了高效地使用數(shù)據(jù)荚虚。
注意這里的關(guān)鍵詞是高效薛夜，一個在分析不同的數(shù)據(jù)結(jié)構(gòu)時你會常常聽說的詞語。
這些數(shù)據(jù)結(jié)構(gòu)提供不同的方式來存儲數(shù)據(jù)版述，以便快速梯澜、動態(tài)地搜索、插入院水、移除腊徙、更新數(shù)據(jù)。
盡管和計算機一樣強大檬某，它們?nèi)匀恍枰噶畈拍芡瓿扇魏斡幸饬x的任務（至少在人工智能出來之前是這樣）撬腾。在此之前你必須給它們盡可能明確、高效的指令恢恼。
如同你可以使用50種不同的方式來建造房子一樣民傻，你也可以使用50種不同方式來組織數(shù)據(jù)。幸運的是场斑，很多聰明的人已經(jīng)構(gòu)建很多偉大的經(jīng)過時間考驗的數(shù)據(jù)結(jié)構(gòu)漓踢。你所要做的就是學習它們是什么，它們?nèi)绾喂ぷ髀┮约霸鯓幼詈玫氖褂盟鼈冃搿Ｏ旅媸且恍┳畛Ｓ玫臄?shù)據(jù)結(jié)構(gòu)列表。我將在后續(xù)文章中逐一介紹它們--本文先介紹棧青责。盡管它們常常有共同之處挺据，但是為了適用于特定的場景取具，這些數(shù)據(jù)結(jié)構(gòu)中每一個都有一些細微差別：
- 棧（Stacks）
- 隊列（Queues）
- 鏈表（Linked Lists）
- 集合（Sets）
- 樹（Trees）
- 圖（Graphs）
- 哈希表（Hash Tables）
你會遇到這些數(shù)據(jù)結(jié)構(gòu)變體，如雙向鏈表扁耐，B-樹以及優(yōu)先隊列暇检。但是一旦你理解了這些核心的實現(xiàn)，要理解這些變體就會很簡單婉称。
所以就從分析棧開始我們的數(shù)據(jù)結(jié)構(gòu)之旅的第一部分块仆。
棧
- 字面意思就是一堆數(shù)據(jù)（就像一堆煎餅）
- 添加（push）--總是添加到棧頂
- 移除（pop）--總是從棧頂開始移除
- 模式類型：先進后出（LIFO）
- 使用范例：使用瀏覽器中的后退和前進按鈕
在許多編程語言中，數(shù)組內(nèi)建了棧的功能王暗。但是為了理解透徹悔据，你將使用一個 JavaScript 對象來重新實現(xiàn)一個棧。
首先你需要創(chuàng)建一個棧用于存儲你訪問過的每一個站點瘫筐，并且在你的棧中創(chuà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() 方法用于返回棧的當前位置隐绵。
在本例中之众，你訪問的每一個網(wǎng)站都將被存放到你的瀏覽器歷史棧中。為了幫助你跟蹤它在棧中的位置依许，你可以用每一個站點的位置作為關(guān)鍵字棺禾，然后每添加一個站點，位置就遞增峭跳。在這里我通過 push 方法實現(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蛀醉，但是因為在 Free Code Camp 上還有一個困難的遞歸問題沒有完成而愧疚悬襟。你決定點擊返回按鈕，回去解決它拯刁。
這一行為在你的棧中是怎么表現(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
通過點擊返回按鈕，將最近添加到瀏覽器歷史的站點移除垛玻，并瀏覽當前處于棧頂?shù)恼军c割捅。你同時遞減了 position 變量，所以你可以準確地表示出你當前處于瀏覽歷史的什么位置帚桩。當然這一切都只有你的棧非空時才會發(fā)生亿驾。
到目前為止看起來都還不錯，但是被移除的對象呢账嚎？
當你解決完問題時莫瞬，決定獎賞自己回去繼續(xù)瀏覽 Netflix参淹，點擊前進按鈕就可以。但是你的棧里有 Netflix 嗎乏悄？為了節(jié)省空間你已經(jīng)將它刪除了浙值，在你的瀏覽器歷史中再也沒有這個站點。
幸運的是檩小，pop 函數(shù)將它返回了开呐，所以也許你可以在別的地方將它存起來以備后用。用另一個棧存起來怎么樣规求！
你可以創(chuàng)建一個 “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
你已經(jīng)使用一種數(shù)據(jù)結(jié)構(gòu)重新實現(xiàn)了瀏覽器基本的前進瓦戚、后退導航！
為了理解透徹丛塌，我們假設你從 Free Code Camp 網(wǎng)站進入以一個全新的站點较解，比如 LeetCode 去做更多的練習。技術(shù)實現(xiàn)上 Netflix 仍然位于你的 forward 棧赴邻，這是沒有意義的印衔。
幸運的是，你可以實現(xiàn)一個簡單的 while 循環(huán)來快速去除 Netflix 以及其他站點：
//When I manually navigate to a new site, make forward stack empty
while(forward.top() > -1){
forward.pop();
}
非常棒姥敛！現(xiàn)在你的導航可以按照預期的方式工作奸焙。
快速總結(jié)一下。棧：
- 1彤敛、遵循 后進先出（LIFO ）規(guī)則
- 2与帆、有用于管理棧內(nèi)內(nèi)容的 push（add） 和 pop（remove） 方法
- 3、有一個 top 屬性用于跟蹤棧的大小以及當前棧頂位置
在這一系列文章中墨榄，每一篇末尾我會對每一種數(shù)據(jù)結(jié)構(gòu)的方法做一個簡單的時間復雜度分析玄糟。
再來看一下代碼：
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)。同樣不需要遍歷就可以移除播揪，因為你總是知道當前棧頂?shù)奈恢谩?/p>
Top：O(1)贮喧。當前位置總是已知的。
棧本身沒有搜索方法猪狈，但是如果你想添加一個箱沦，你想一下時間復雜度應該是什么？
Find(查找) 應該是 O(n)雇庙。技術(shù)上你必須遍歷存儲的內(nèi)容知道找到你查找的內(nèi)容谓形。這就是數(shù)組的 indexOf 方法的本質(zhì)灶伊。
本文譯自：A Gentle Introduction to Data Structures: How Stacks Work
