棧在資料結構中的應用

棧是後進先出 (LIFO) 的資料結構。這種資料結構在不同方面有一些重要的應用，如下所示：

• 表示式處理：

  • 中綴表示式轉字尾表示式或中綴表示式轉字首表示式：

    棧可以用於將某些中綴表示式轉換為其等效的字尾表示式或字首表示式。這些字尾或字首表示法用於計算機表達某些表示式。這些表示式與中綴表示式不太熟悉，但它們也有一些很大的優勢。我們不需要維護運算子順序和括號。

  • 字尾表示式或字首表示式的求值：

    轉換為字首或字尾表示法後，我們需要計算表示式以獲得結果。為此，我們也需要棧資料結構的幫助。

• 回溯過程：

  回溯是演算法設計技術之一。為此，我們深入研究某種方法，如果該方法效率不高，我們會回到之前的狀態，並嘗試其他路徑。要從當前狀態返回，我們需要儲存先前狀態。為此，我們需要棧。回溯的一些例子包括尋找騎士巡遊問題或 N 皇后問題的解等。

• 棧的另一個重要用途是在函式呼叫和返回過程中。當我們從另一個函式呼叫一個函式時，該函式呼叫語句可能不是第一個語句。呼叫函式後，我們還必須從函式區域返回到我們離開控制的地方。因此，我們希望恢復我們的任務，而不是重新啟動。為此，我們將程式計數器的地址儲存到棧中，然後轉到函式體執行它。執行完成後，它從棧中彈出地址並將其分配給程式計數器以再次恢復任務。

Arnab Chakraborty

更新於：2019年8月27日

3K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習