DOUG LLOYD：好吧， 所以通過這點你 可能很熟悉 數組和鍊錶 這是兩個主要 我們已經數據結構 談到保持套 類似的數據類型的數據組織的。 現在我們要談 約上幾個變化 對數組和鍊錶。 在這個視頻中，我們要去 談棧。 具體來說，我們要談 有關的數據結構稱為堆疊。 從前面的討論召回 關於指針和內存， 堆棧也是 命名為的存儲器段 其中，靜態聲明 memory--內存，你 名稱，命名變量，等 等等和功能框架，我們也 調用堆棧幀的存在。 所以這是一個堆棧數據結構 記憶不是一個堆棧段。 確定。 

但什麼是棧​​？ 所以這是非常簡單，只是一個 特殊的結構 在一個有組織的方式保持數據。 而且還有兩個很 常見的方式來實現 棧使用兩個數據結構 我們已經很熟悉了， 數組和鍊錶。 是什麼讓一個堆棧特別是 以何種方式，我們把信息 入堆棧，這樣我們的方式 請從堆棧信息。 尤其是對於棧 規則是只有最 最近添加的元素可以被刪除。 

這樣想來，好像它是一個堆棧。 我們正在打樁信息 其本身上， 只有東西在頂部 樁的可以去掉。 我們不能下刪除的東西 因為一切會 折疊和翻倒。 所以，我們真的正在建設一個棧 然後，我們必須逐件除去件。 正因為如此，我們通常所指 到堆棧作為LIFO結構， 後進先出。 後進先出法，後進先出。 

所以這個限制的，因為 信息如何可以被添加到 而從堆棧中刪除，沒什麼 只有兩件事情，我們可以用堆棧來。 我們可以推動，這是 我們長期使用的添加 一個新元素的頂部 疊，或者如果棧不存在 我們正在從頭開始創建它， 創建堆棧擺在首位 將推動。 然後彈出，這是CS的那種 長期我們用它來刪除最近 從堆棧的頂部添加元素。 

因此，我們要看看這兩個 實現，無論是基於陣列的 和鍊錶為主。 而且我們要 開始的數組。 因此，這裡的基本想法是什麼 在基於陣列的堆棧數據結構 會是什麼樣子。 我們在這裡有一個類型的定義。 裡面的，我們有兩個成員 結構或字段。 我們有一個數組。 又一次我使用的 任意數據類型的值。 

因此，這可以是任何類型的數據， INT char或其他一些數據 你以前創建的類型。 因此，我們有大小容量的陣列。 容量正在一斤定義的常量， 也許別人在我們的文件的地方。 因此，與這個特定的已通知 實現我們的邊界 自己作為是典型的 數組的情況下， 這是我們無法動態調整， 那裡有一定數量 最大元素 我們可以把我們的堆棧。 在這種情況下，它的電容元件。 

我們也跟踪 堆棧的頂部。 什麼元素最重要的是 最近添加到棧？ 因此，我們持續跟踪 在一個變量被稱為頂端。 而所有這一切都被包裹起來 成稱為棧一個新的數據類型。 而一旦我們創建 這個新的數據類型 我們可以把它像 任何其它數據類型。 我們可以聲明堆棧S，就像 我們可以做INT x或字符年。 而當我們說堆棧 S，以及會發生什麼 是我們得到了一組 內存預留了我們。 

在這種情況下，容量 我顯然決定 是10，因為我有一個 型堆的單可變 其中包含兩個字段回憶。 的陣列，在這種情況下，會 是一個整數數組 因為在我的大部分例子的情況。 而另一位整型變量 能夠存儲的頂部， 最近添加 元件到堆棧中。 因此，一個單一的堆棧我們 剛剛定義看起來像這樣。 它包含一個盒子 的10的陣列什麼 將在這種情況下，整數和 在綠色的另一個整型變量有 以指示堆棧的頂部。 

要設置的頂部 堆棧，我們只是說s.top。 這就是我們訪問 場的結構召回。 s.top有效等於0 這樣做是為了我們的堆棧。 所以，再一次，我們有兩個操作 我們現在可以執行。 我們可以把我們可以彈出。 讓我們先從推動。 再次，推是添加了新的 元素添加到堆棧的頂部。 

那麼，我們需要做的 這種基於陣列的實現？ 那麼一般 推送功能會 到需要接受 指針到堆棧。 現在，花一秒鐘想想。 為什麼我們要接受 指針堆棧？ 從以往的視頻回憶 變量的作用域和指針， 如果我們只是派會發生什麼 堆棧，S而作為一個參數？ 但實際在那裡被傳遞？ 請記住，我們正在創建一個副本 當我們把它傳遞給函數 除非我們使用指針。 所以這個功能推動需求 以接受的指針堆棧 讓我們實際上改變 堆棧，我們打算改變。 

另一件事推可能要 接受的類型值的數據元素。 在這種情況下，再次，一個整數， 我們要添加到堆棧的頂部。 因此，我們有我們的兩個參數。 什麼是我們要 現在做俯臥撑裡面？ 好了，簡單地說，我們只是要添加 該元素到堆棧的頂部 然後更改的，其中的頂部 堆棧，使得S點頂部的值。 因此，這是一個函數 聲明推 可能看起來像在 基於數組的實現。 

同樣，這不是一個硬性規定 你可以改變這一點，有 它以不同的方式而變化。 也許s的全局聲明。 所以你甚至不需要 通過它是作為一個參數。 這又是只是一個 一般情況下推動。 也有不同 的方式來實現它。 但在這種情況下，我們 推是要採取 兩個參數，一個指向一個堆棧和 類型值，整數的數據元素 在這種情況下。 

因此，我們宣布S，我們 說s.top等於0。 現在讓我們來推 28號到堆棧中。 那麼這是什麼意思？ 那麼目前 棧頂部是0。 所以，什麼是基本 事情發生是 我們要堅持數 28到數組的位置0。 很簡單，對了，那 是頂部，現在我們是好去。 然後，我們需要改變什麼 堆棧的頂部會。 因此，下一次 我們推入一個元素， 我們將其存儲在 陣列位置，可能不是0。 我們不希望覆蓋 我們剛才放在那裡。 所以我們只將頂到1。 這可能是有道理的。 

現在，如果我們想要把另一個元素 壓入堆棧，說我們要推33， 現在好了，我們只是將採取33 並把它在數組位置數 1，然後更改的頂部我們 堆棧是數組位置排名第二。 因此，如果在下一次我們要 推一個元素入棧中， 它會被放在數組位置2。 而讓我們做一個更多的時間。 我們將推動19關棧。 我們將投入19陣列的位置2 和改變我們的堆棧的頂部 要陣列的位置3 所以如果下一次我們 需要做一個推，我們是好去。 

OK，所以這是推動概括地說。 什麼大跌眼鏡？ 所以大跌眼鏡的是排序 對口推。 這是我們如何從堆棧中刪除數據。 而在一般流行音樂的需求 做到以下幾點。 它需要接受的指針 疊，再在一般情況下。 在其他一些情況下，你可能 已宣布在全球範圍堆棧， 在這種情況下，你不需要將它傳遞 在因為它已經訪問了它 作為全局變量。 但隨後還有什麼需要我們做什麼？ 嗯，我們都遞增 疊推的頂部， 所以我們可能會想 遞減堆棧的頂部 在流行音樂，對不對？ 然後當然 我們也將要 回到我們刪除值。 如果我們要添加的元素，我們希望 得到的元素出來以後， 我們可能實際上 要存儲他們，所以我們 不只是從刪除 堆棧中，然後什麼也不做他們。 一般來說，如果我們 推和彈出在這裡 我們要存儲此 以有意義的方式信息 因此它不會使 感覺只是丟棄它。 所以這個功能應該 可能返回一個值給我們。 

因此，這是一個多麼聲明流行 可能看起來像有在左上角。 該函數返回 類型值的數據。 我們再次使用已經 整數貫穿始終。 和它接受一個指向一個堆棧 其唯一的參數或唯一的參數。 那麼，什麼是流行音樂該怎麼辦？ 比方說，我們希望現在 流行元素斷號第 所以請記住我說的堆棧是最後一個 先出，後進先出的數據結構。 該元件是要 從棧中刪除？ 你猜19？ 因為你是對的。 19是我們加入的最後一個元素 當我們在推動元件堆疊， 所以它會第一 元素被刪除。 這是因為如果我們說28，和 然後我們把33在它的上面， 我們把19最重要的是。 我們可以脫下唯一的元素是19。 

現在，這裡的圖中我做了什麼 是那種從陣列中刪除19。 這實際上不是 我們要做的。 我們只是來樣 中假裝它不存在。 它仍然存在於 該內存位置， 但我們只是要忽略它 通過改變我們的堆棧的頂部 從為3至2。 所以，如果我們現在推 另一元件壓入堆棧， 它會在寫19。 

但是，我們不要經歷的麻煩 中刪除19從堆棧中。 我們可以假裝它不存在。 為了堆棧就不見了，如果 我們改變頂端是2而不是3。 好了，所以這是相當多了。 這就是我們需要做的 流行元素了。 讓我們再次做到這一點。 所以，我已經強調了它在紅色這裡 表明我們正在做另一個電話。 我們將做同樣的事情。 

那麼，什麼會發生？ 好了，我們要保存 33 x和我們要去 到堆棧的頂部改變到1。 所以，如果我們現在推的 元素進棧，我們是 要做的事情，現在， 什麼會發生 是我們要覆蓋 陣列位置號碼1。 所以這33類中所剩下的 後面，我們只是假裝 不存在了，我們只是 要破壞它，並把40同去。 然後，當然， 因為我們做了一個推， 我們要遞增 棧頂部1〜2 這樣，如果我們現在添加 另一種元素，它會 進入陣列的位置排名第二。 

現在鍊錶是另一種 方法來實現堆棧。 而如果在這個定義 屏幕這裡看起來很熟悉你， 這是因為它看起來幾乎 完全相同的，事實上， 它幾乎是完全 同一個單向鍊錶， 如果你從我們的討論召回 在另一個視頻單鍊錶。 這裡的唯一限制 對我們來說是程序員， 我們不允許 插入或刪除隨機 從單向鍊錶 這是我們可以做以前。 只是現在我們可以插入和刪除從 前面或的連接的頂端 名單。 這真的是唯一的 區別不過。 這是否則單鍊錶。 這是唯一的限制 替換上自己 作為程序員 改變成一個堆棧。 

這裡的規則是始終保持 指針的一個鍊錶的頭部。 當然，這是一個通常 第一個重要的規則。 對於單向鍊錶，反正你 只需要一個指向頭部 為了有 鏈能夠參考 至所有其他元素 在鍊錶。 但它是特別 重要用棧。 所以一般你 要真正想要的 這個指針是一個全局變量。 它可能會 可以更容易的方式。 那麼什麼是push和pop的類似物？ 右。 所以推再次增加 一個新的元素到堆棧。 在一個鍊錶 意味著我們將有 創建一個新的節點，我們是 將添加入鍊錶， 然後按照謹慎的步驟 我們先前已經介紹 在單鍊錶將其添加到 不破壞鏈的鏈 和丟失或成為孤兒的任何 鍊錶元素。 而這基本上是什麼 文本的小斑點有總結。 讓我們一起來看看 它作為一個圖。 

因此，這裡是我們的鍊錶。 它同時包含四個要素。 而更加完美地在這裡是我們的 堆棧包含四個元素。 而且，我們說，我們現在要 推新項目到這個堆棧中。 我們要推新 其數據的價值產品12。 那麼我們怎麼辦呢？ 那麼首先我們要 malloc的空間，動態 分配空間用於新的節點。 當然，緊接著又 我們打電話到我們的malloc始終 一定要檢查空， 因為如果我們得到了空回 有某種問題。 我們不希望取消引用的空 指針，否則就慘了賽格故障。 這不是很好。 因此，我們已經malloced節點。 我們假設，我們已經在這裡取得了成功。 我們打算把12進 該節點的數據字段。 現在，你還記得，我們​​的指針 移動下一個，所以我們不打破鏈？ 我們有幾個選項，在這裡，但 是唯一一個將是安全的 是集新聞下一指針 指向老首長名單 或者是不久將成為 老首長的名單。 而現在，我們所有的 元素鏈接在一起， 我們只要將名單指向 那個新不一樣的地方。 現在我們已經有效地推了 新元件壓入堆棧的前面。 

要跳出我們只是想 刪除第一個元素。 所以基本上是什麼 我們要在這裡做， 同時，我們必須找到第二個元素。 最終，這將成為新的 頭後，我們刪除了第一個。 所以，我們只需要從開始 開始的時候，移動一個前鋒。 一旦我們已經有了一個保持在一個 在那裡，我們期待目前 是我們可以安全地刪除第一個 然後我們就可以將頭 指向究竟是什麼 第二項，然後現 是之後，第一 節點已被刪除。 

如此反复，考慮看看 它作為一個圖，我們 希望現在流行的 元素關閉該堆棧。 那麼我們該怎麼辦？ 那麼我們首先要創建 一個新的指針是怎麼回事 為指向相同的位置為頭。 我們要移動一個位置 向前說TRAV等號 TRAV接下來為例，它 將推進TRAV指針1 位置前移。 現在，我們已經有了一個 保持第一元件上 通過該指針叫列表，以及 通過指針稱為第二元件 TRAV，我們可以安全地刪除 從棧第一元件 不失休息 鏈，因為我們 有辦法參考 到第二元件 由前進的道路 指針稱為TRAV。 

所以，現在我們可以免費在該節點。 我們可以免費列表。 然後將所有我們現在需要做的是 移動列表指向同一個地方 這TRAV做，而且我們的排序回 我們開始的地方，我們推12日前 在第一地點，合適。 這正是我們在那裡。 我們有這四款元素堆棧。 我們增加了五分之一。 我們推第五 元素，然後我們 殺出，以最近 加元回退。 

這真是非常 所有有棧。 您可以實施他們作為陣列。 您可以執行這些鍊錶。 還有，當然，其他 方法來實現它們。 基本上，我們將使用的原因 棧是維持在這樣的方式的數據 該最近添加 元素是我們的第一件事情 會想回去。 我是道格·勞埃德，這是CS50。