爲什麼和什麼時候應該使用堆棧或隊列數據結構而不是數組/列表?你能舉一個例子說明,如果你使用堆棧或隊列,它會更好嗎?堆棧和隊列,爲什麼?
回答
因爲它們以比數組和列表更特殊的方式幫助管理數據。
隊列是先入先出(FIFO)
堆棧是後進先出(LIFO)
數組和列表是隨機接入。它們非常靈活,也很容易腐敗。如果您希望將數據作爲FIFO或LIFO來管理,最好使用已經實施的那些集合。
當您想要在您的數據結構上實施某種使用模式時。這意味着當你調試一個問題時,你不必懷疑某人是否隨機地將一個元素插入列表的中間,搞亂了一些不變量。
- 當你想要得到的東西出來的順序,你把他們在使用的隊列中。
- 當你想要得到的東西出相反的順序比你把他們在使用堆棧。
- 無論您何時放入(以及何時不希望它們自動移除),您都可以使用列表獲取任何內容。
這是一個意圖問題。堆棧和隊列通常使用數組和列表來實現,但是元素的添加和刪除更加嚴格。
棧或隊列是一個邏輯數據結構;它將在具有物理結構(例如列表,陣列,樹等)的封面下實現。
如果您願意,或者利用已經實現的抽象,歡迎您「推出自己的產品」。
除了其他人已經提到的使用強制執行之外,還有一個性能問題。當你想從一個數組的開頭或一個List(ArrayList)中移除某些東西時,它通常需要O(n)次,但對於一個隊列則需要O(1)次。如果有很多元素,這可以產生巨大的差異。
問題不明確,因爲您可以使用數組或鏈接數據結構表示堆棧或隊列的抽象數據類型。
堆棧或隊列的鏈表實現與數組實現之間的區別與任何數組與動態數據結構具有相同的基本折衷。
鏈接隊列/鏈接堆棧具有靈活,高速的插入/刪除和合理的實現,但需要比陣列更多的存儲空間。插入/刪除在陣列末端便宜,直到用盡空間;隊列或堆棧的數組實現需要更多的工作來調整大小,因爲您需要將原始數據複製到更大的結構中(或者發生溢出錯誤)。
數組/列表和堆棧/隊列不是互斥的概念。事實上,您發現的任何堆棧或隊列實現幾乎可以肯定地使用陣列或引擎蓋下的列表。
數組和列表結構提供了數據如何存儲的說明,只要保證結構上基本操作的複雜性即可。
堆棧和隊列給出瞭如何插入或刪除元素的高級描述。隊列FIFO,堆棧FILO。
例如。如果你正在實現一個消息隊列,你將使用一個隊列。但是隊列本身可以將每條消息存儲在一個列表中。 「推送」添加到列表前面的消息,「彈出」列表末尾的消息。
堆棧和隊列是更高級的方式來處理數組本身的集合,該集合本身不會以元素在集合中的行爲方式建立任何順序。
堆棧(LIFO - 後進先出)和隊列(FIFO - 先進先出)建立並排序元素插入到集合中並從中移除。
您可以使用數組或鏈接列表作爲存儲結構來實現堆棧或隊列模式。甚至可以使用這些基本結構創建更復雜的模式,如二叉樹或優先級隊列,這可能不僅會導致插入和移除元素的順序,還會在集合中對它們進行排序。
你去過一家自助餐廳吧?看到一堆盤子?當一個乾淨的盤子被添加到堆棧時,它被放在最上面。當平板被移除時,它會從頂部移除。所以它被稱爲後進先出(LIFO)。一個計算機堆棧就是這樣,除了它包含數字,並且如果你喜歡,你可以從數組或列表中創建一個。 (如果堆疊的盤子下面有一個彈簧,他們說你「推」一個到頂部,當你移除一個時,你會「彈出」它。)
在食堂,回去,他們在那裏洗碗。他們有一條傳送帶,在那裏他們把盤子一端洗淨,然後從另一端排出,順序相同。這是一個隊列或先進先出(FIFO)。如果你願意的話,你也可以從數組或列表中創建一個。
它們有什麼用?那麼,假設你有一個樹形數據結構(它像木頭製成的真正的樹,除了它是顛倒的),並且你想寫一個程序完全穿過它,以便打印出所有的葉子。
一種方法是做一個深度優先散步。你從樹幹開始,轉到第一個分支,然後轉到該分支的第一個分支,依此類推,直到你到達葉子並打印出來。但你如何備份到下一個分支?那麼,每次你下了一個分支時,你都會「推」一些信息到你的堆棧中,而當你備份時,將它「彈出」回來,並告訴你下一個分支。這就是你如何跟蹤每個點下一步要做哪個分支。
另一種方式是寬度優先散步。從中繼線開始,將所有分支從中繼線上編號,並將這些號碼放入隊列中。然後你從另一端取一個數字,轉到那個分支,並且對於每個分支從開始,你再次對它們進行編號(與第一個連續)並將它們放入隊列中。當你繼續這樣做時,你將首先訪問距離樹幹1分支的樹枝。然後,您將訪問距離行李箱2個分支的所有分支,等等。最終你會到樹葉上去打印它們。
這些是編程中的兩個非常基本的概念。
我認爲堆棧和隊列都是內存訪問的概念,根據應用需求使用。另一方面,數組和列表是兩種內存訪問技術,它們用於實現堆棧(LIFO)和隊列(FIFO)概念。
- 1. 爲什麼要實現堆棧和隊列java
- 2. 爲什麼我們在Java中使用堆棧和隊列?
- 3. 堆棧和隊列用java
- 4. 隊列+堆棧C++
- 5. 爲什麼會有堆棧和堆?
- 6. 爲什麼使用兩個堆棧來創建一個隊列?
- 7. 堆棧和隊列在編程中提到什麼?
- 8. 堆棧爲空...爲什麼?
- 9. 使用隊列堆棧
- 10. 堆棧和隊列的使用情況?
- 11. 比較隊列和堆棧的內容
- 12. 可觀察堆棧和隊列
- 13. 堆棧和隊列奇怪的錯誤
- 14. cuda中的遞歸/堆棧和隊列
- 15. 爲什麼堆棧有界?
- 16. 什麼「堆棧無效,堆棧只支持堆棧1和堆棧5」是什麼意思?
- 17. 爲什麼環繞隊列對於堆棧而言是必要的,而不是堆棧?
- 18. 基於陣列和基於列表的堆棧和隊列
- 19. 列表,數組,堆棧隊列?
- 20. 堆棧vs排隊?
- 21. 爲什麼堆棧結束爲空?
- 22. 我想實現一個隊列,將反轉堆棧和打印堆棧FIFO?
- 23. C++堆棧/堆棧。爲什麼只有一個新操作員?
- 24. 進程堆棧和CPU堆棧有什麼區別?
- 25. 調用堆棧和堆棧跟蹤有什麼區別?
- 26. 線程堆棧和進程堆棧有什麼區別
- 27. 爲什麼我們要在堆棧和堆上管理結構
- 28. 爲什麼內存分成堆棧和堆?
- 29. 爲什麼堆棧和堆都需要內存分配
- 30. 使用2堆棧實現隊列
堆棧和隊列用數組和列表實現。 – Yada 2010-01-15 21:43:36
您可能想查閱數據結構上的文本。這是所有CS和DP學生的基本要求。 – 2010-05-08 15:49:09