搜索簡單的問題，使用堆棧

Question

我想知道簡單的問題，可以使用自然堆與通常的接口（emptyS，isEmptyS，push，pop，top）解決自然解決。

與問題的上下文相關的複雜性應爲空。我目前無法觸及解析，編譯或搜索算法等主題。這拋棄了許多經典例子。

我迄今發現的最美麗的例子是檢查字符串中的平衡括號。在很少的幾行中，沒有任何其他背景，練習顯示了數據結構的實用性：

另一個很好的例子是處理一個字符串，其中星號表示從棧中彈出一個項目，而一個字母表示將它推入堆棧。該函數必須在將字符串中描述的操作應用於空堆棧後返回堆棧。

如果你可以分享一些其他問題，我會非常讚賞它。

預先感謝您。

Answer 1

雖然這個問題太廣泛了，但我還是會給出一些其他的應用。一些其他常見的應用是 -

1. 解析
2. 遞歸函數
3. 調用功能
4. 表達式求值
5. 式變換
   • 綴以後綴
   • 綴前綴
   • 後綴以綴
   • 前綴綴
   河內

一些細節的

塔可以找到here。