C++中的堆棧。他們爲什麼以及何時使用？

閱讀了關於堆棧的章節（第7章，使用C++第2版的數據結構，D.S.Malik）。我似乎遇到了麻煩，無法理解在C++中使用堆棧的概念。C++中的堆棧。他們爲什麼以及何時使用？

我明白堆棧本身是一種數據類型，主要用於LIFO（後進先出）編程風格。有堆棧可以提供使用的函數...例如pop,push,isEmpty,isFull和top但我不完全瞭解每個人完全做什麼以及他們如何一起工作。

他們在'大圖片'中使用了什麼？在編寫代碼時如何才能認爲堆棧有用？

任何解釋或例子都會非常有幫助！

謝謝，

來源

2014-10-03 ALMorrow

你的意思是，爲什麼LIFO數據結構是有用的？ – 2014-10-03 21:08:59

您是否想了解如何在C++中實現堆棧？或者你想知道一般來說堆棧是有用的嗎？如果你的意思是一般性問題，這不是一個C++問題。 – 2014-10-03 21:09:51

是的，我想了解如何在C++中實現堆棧@David K – ALMorrow 2014-10-03 21:14:50

有很多特定的情況下，你可能想要使用一個堆棧。那些想到的是

將「正常」中綴數學表達式轉換爲後綴或前綴表達式。
評估一個數學表達式。
穿越迷宮。

來源

2014-10-03 21:10:58

等等。檢查：http://en.wikipedia.org/wiki/Stack_(abstract_data_type） – 2014-10-03 21:11:31

堆棧用於各種算法。一些示例：

以迭代的等效
parralelizing遞歸算法平移遞歸算法（需要一個線程安全堆棧實現）
實現深度第一圖形搜索，當相同的算法與隊列會給你先呼吸一下。
執行後綴表達式
等...

關於棧的一般原則：

在beginining，堆棧是空的。通常需要檢查堆棧是否爲爲空，以瞭解是否有更多要處理的元素。
堆棧的固定大小實現需要在嘗試存儲新元素之前檢查空間是否空閒。
push在堆棧的頂部放置了一個新元素，從而增加了元素的數量。
pop從堆棧頂部取得元素（即最後一個被推入的元素）並減少堆棧。
top讀取堆棧的頂層元素，但將其保留在沒有修改堆棧的位置。

關於top和pop的註釋：在傳統的堆棧（例如：CPU的彙編程序）中，pop讀取堆棧的頂部並將其刪除。但是許多實現將頂層元素中的兩個操作分開，並彈出（刪除頂層元素）。

我建議您熟悉std::stack，這與您的書有些不同（至少對於操作的命名），但是立即可用。

來源

2014-10-03 21:12:59 Christophe

我只是檢查了我的代碼庫，而我使用的是類棧的數據結構中的唯一的地方是：

當解析腳本的詞法階段，以匹配括號的位置，只是爲了更好的錯誤信息。
在評估腳本期間，如果我需要在腳本完成之前（即在「睡眠」呼叫期間，以便其他代碼仍可以運行）返回，我可以保存「環境」。

對我來說，使用遞歸調用（即硬件堆棧）或者想要一個set或一個隊列更爲常見。

來源

2014-10-03 21:24:12 o11c

是的，遞歸非常好！但不幸的是，硬件堆棧在某些環境中的大小有限。此外，優化器可以在循環上執行更好的工作（f.ex.找到循環不變量），而不是遞歸調用。 – Christophe 2014-10-03 21:42:40

@Christophe我不相信通常會教壞習慣，因爲有一些*系統在那裏只有很小的堆棧。我的經驗是，遞歸更容易優化，因爲它更有可能是功能性的（即具有不可變的變量）。 – o11c 2014-10-03 21:55:49

很多年前，它曾經是一個函數調用的固定開銷如此之大，編譯器優化得如此之差，以至於您可以通過實現自己的堆棧而不是使用調用堆棧來加速一些深度遞歸。現在這似乎不太常見。 – 2014-10-06 21:44:34

我在我的編譯器中使用了一個堆棧來跟蹤每個「範圍」中的局部變量和類型 - 因爲它是一個Pascal編譯器，所以它允許嵌套函數以及每個嵌套級別的一組新的變量和類型。所以，我有一個堆棧，它以全局變量開始，然後爲每個函數級別添加另一層堆棧。當功能是「完成」時，堆棧被「彈出」去除該層。

堆棧被用於許多其他性質的事情，換句話說，你有層次的東西。你可以打破一個數學表達式爲：

x = a + b * (d - e);

所以，我們發現x =，看看接下來會發生什麼：它不只是一個單一的variabe，所以我們必須把它分解成幾部分：

a + b,

但接下來是*，它的優先級高於+，所以我們需要推動我們到目前爲止的a,+和b，並首先計算*某事。在括號內，所以我們必須推動*，並計算d - e。現在我們可以開始走回棧底：pop給我們*然後b，所以把它們相乘，然後再彈出，這會給出+和a。最後我們得到=和x，所以我們做這個任務。（儘管在我的編譯器項目中，我只是通過從二元運算符分析器中調用二元運算符分析器來解決此問題）。很多遊戲「嘗試不同的選擇」（數獨求解器，國際象棋，井字棋，迷宮發現等）使用遞歸或堆棧來跟蹤「我們有什麼選擇」，其中每個進一步的移動是另一層在堆棧上。再次，它可以通過定期遞歸或使用堆棧來完成。簡單列舉此時可能的「動作」，選擇一個並做出該動作，然後對對手執行相同的操作（假設它是雙向遊戲，而不是數獨或迷宮），等等。每個「玩過的步驟」都是一個堆棧層次。如果你找到一個「好」的，在存儲「這是正確的行動」之後回溯 - 如果它走得很糟糕，那麼用「不是一個好的舉動」來回溯（例如，在國際象棋中，許多舉動可能是「好的」（因爲有多種選擇，或者因爲有太多的選擇，我們無法嘗試每一種方式來「贏/輸」情況）和一些「壞」，所以你必須得到「如何好「是]。

還有很多其他的事情，「我需要記住我之前在哪裏，以便我可以在以後回來」。

來源

2014-10-03 21:36:33

編輯：在我原來的答案，我傻傻忽視已有的STL 棧的實現，std::stack。這有push,pop和top函數完全符合您的期望，而empty函數實現了isEmpty()函數。

例如，爲了使my_stack_instance是整數堆棧，你可以簡單地聲明

std::stack<int> my_stack_instance;

沒有「isFull」操作本身。如果超過容量，std::stack應該「增長」（在更大的內存塊中重新分配本身）。

我以前的建議是使用std::vector。理想情況下，它不會是您的堆棧對象，它會是在您的堆棧對象，以便您可以使用有意義的名稱公開功能而不公開您不需要的函數。如果你使用std::stack那麼它不如是你的堆棧對象，因爲它已經暴露了它應該的功能。

如果您必須實施一個堆棧以證明您理解某個類，則可能不會接受，然後std::stack。然後，我會與你的老師挑選關於使用C++作爲「教學」語言，但我認爲這是一個不同的主題，。

來源

2014-10-03 21:50:56

C++中的堆棧。他們爲什麼以及何時使用？

回答

相關問題