棧和佇列是操作受限線性表,操作限制降低了操作靈活性,為什麼要加入這些限制?

時間 2021-05-06 23:11:04

1樓:王輝

你要把自己當成乙個服務提供者,假如你提供了佇列和棧的服務,那麼介面上給的越少,你對別人的承諾就越少,因此你自己受的限制就越少,好維護,好發展。這是設計介面的最重要原則。

2樓:劉源

計算機的核心部分是比較數學化的。

軟體開發中,有乙個核心問題就是「如何組織資料進行計算」。例如:

有乙個網路事件源,需要逐個處理事件,但是一次處理不完,怎麼辦?

網路拓撲圖中,如何檢查兩點間是否聯通?

乙個函式可能輾轉又呼叫了自己,那麼他的區域性變數存到什麼地方?

有很多介面,希望使用者點回退的時候,回到上個介面,怎麼辦?

資料結構和演算法,就是形式化的解決了「如何組織資料進行計算」這個問題,以Knuth《計算機程式設計的藝術》為代表,在上世紀60年代末期就研究完畢,成為系統的理論。其中資料結構部分的關鍵就是:

歸類最重要資料結構,並解決一系列典型問題

此後,工程問題就可以將資料結構作為「積木」搭建 —— 實際上大家也是這麼做的 —— 然後你就可以在「資料結構」層描述問題的解法。

回到剛才的問題,答案可以是:

網路事件源:佇列

網路拓撲圖:佇列可以進行廣度優先遍歷;棧可以進行深度優先遍歷

函式呼叫:棧

介面回退:棧

佇列和棧是這個問題的數學本質,結構本質。乙個先進先出,乙個先進後出。《資料結構》充分分析了這兩種結構,乙個定義為「佇列」,乙個為「棧」,並指出他們是O(1)的方案,最後用一批經典問題進行了訓練

下層可能是陣列或者鍊錶這樣更基礎的結構,幷包含瑣碎細節。然而,那些在這裡並不重要。你可以在棧、佇列層次直接考慮問題。

具體這兩個是那麼受限呢,總的來說就是「沒必要」。

小而美是一種工程設計哲學。C++ stl,或者C# linq的API設計,都是用受限結構來提高泛用性(其中C++更加原教旨)。所以最終實踐上,棧和佇列往往沒有提供中途插入功能。

3樓:繁星雨夜

其實,這是乙個哲學問題。

老子曾經說過:三十輻共一轂,當其無,有車之用。埏埴以為器,當其無,有器之用。鑿戶牖以為室,當其無,有室之用。

翻譯過來就是:三十根輻條匯集到一根轂中的孔洞當中,有了車轂中空的地方,才有車的作用。揉和陶土做成器皿,有了器具中空的地方,才有器皿的作用。

開鑿門窗建造房屋,有了門窗四壁內的空虛部分,才有房屋的作用。所以,「有」給人便利,「無」發揮了它的作用。

這裡「有」相當於棧等資料結構,「無」相當於記憶體。

回到記憶體來說,一片記憶體是可以隨意讀寫的。但是其實,自由==複雜。限制==簡單。

記憶體可以有很多種的用法,但是在某一種場景下,我們只需要其中一種用法,而如果我們把不需要的用法完全剝離出去,那留給我們的就是乙個簡單易用的方法,也賦予了這片記憶體的意義和功能。

4樓:PegasusWang

棧幾乎只用 push,pop 操作棧頂元素,佇列一般也只在兩頭操作。之所以用線性表是因為場景適合、實現簡單。而且這兩種結構一般不會涉及到隨機訪問。

說白了是資料結構的選取問題,根據具體問題分析選用什麼資料結構。

5樓:

作為容器,要麼有排序規則,要麼有分類規則。」棧和佇列「,實現了兩種最簡單的」排序規則「。

你自己的理解角度有問題。

作為容器的使用者,你是「上帝」。在上帝視角裡,你能感覺到「操作不靈活」。可是作為容器的設計者,他怎麼可能知道」操作靈活性「?

你能否把」操作不靈活「,總結成」排序規則「。說白了,」操作靈活性「是否是某種」確定性「?

6樓:

適用性越廣 => edge case 越多 => 時間複雜度越高。多少 deepclone 耗在了解決迴圈索引?

要操作靈活可以不用棧或佇列呀,不就有各種樹和圖嗎?像樂高一樣,如果整個盒子裡都是奇形怪狀的,還怎麼玩

做組合也是個方法,Segment Tree, Hash Heap 就這麼來的

7樓:命中十環

沒有所謂「限制」,是應用場景決定了工具屬性。比如在流水線上擰螺絲這個場景下,只需要配套螺絲刀這種專用工具。如果非要加上切割、開罐頭之類的功能,變笨重影響工作效率(效能)不說、還無謂增加成本(空間)。

8樓:北南

使用棧和佇列這些抽象資料型別可以幫助我們更有效率的解決複雜問題。

其實棧和佇列都是一種對資料的封裝(encapsulation),封裝後,很多內部細節就對外部隱藏了(這個就是資訊隱匿information hiding的概念)。這樣做的好處是,咱們程式設計師就可以更好的關注大局,但同時有不喪失對資料的必要操作。

另外,抽象資料型別(棧和佇列)讓你的資料結構和具體實現無關了。棧和佇列可不一定是乙個簡單直接的線性表哦。比如說乙個棧,可以背後用陣列實現,用鍊錶實現,用資料庫實現,用檔案實現,用分布式快取實現。

只要他提供pop和push介面,能滿足先進後出的特性,就是乙個棧。而當我使用乙個棧的時候我就不去關心他的具體實現,而只關注與我的具體演算法。

9樓:鼓趙

你做飯為了切菜買了個菜刀,臨了出超市把收銀員砍了。跟警察局說為什麼菜刀要加上這種限制?不也能砍人嗎?

你看警察刑不刑訊了你。

10樓:沈萬馬

因為物理這種討厭的鬼東西的存在。

計算機理論世界裡一切都那麼美好對吧。資料往記憶體裡一丟就行了,位址空間無限大,哪兒都有任意長度的連續記憶體,誰都只要知道變數名或者指標就能找到你要的資料,所有訪問都是O(1),所有資料都可以任意時間寫入時複製,所有已分配空間都可以O(1)列舉而且還能自動跳過無引用的部分。

可惜現實世界裡有魔鬼啊。記憶體有限,位址空間有限,連續空間有限,對記憶體的引用本身要消耗記憶體,……

於是為了方便我們使用記憶體,大家創造了棧、佇列等結構,通過犧牲一些東西來換取需要的特性。有的犧牲隨機訪問能力來節省空間,有的浪費空間來避免占用大段連續記憶體,有的占用大段連續記憶體來使隨機訪問能多快多快…

11樓:小舟從此逝

這兩個都是抽象。抽象一般是為了簡化,即僅僅提取出必要的部分或性質。簡化的好處可能有很多,具體到棧和佇列上,比如思考起來更容易,比如應用範圍更廣泛(稍微展開下:

陣列靈活性是建立在記憶體可隨機訪問的性質上;假如儲存介質不支援隨機訪問、只支援先進後出或先進先出,顯然這種情況下基於棧或佇列的抽象就會非常有用)。

12樓:謝勇

你可以用菜刀切土豆絲,但刮絲器更方便;你也可以用菜刀削黃瓜皮,但是刮皮器更方便。菜刀是不是更靈活了?特定的資料結構和演算法都是針對具體問題的,有它適用的場景。

13樓:張軒銘

學習資料結構,我們不要太死板,棧和佇列的相關操作只是我們自己的人為規定,只不過這樣的操作在實際中太常用了,所以大家就把它規範起來,然後取個名字,就是這樣。

之所以有這樣的規定,是因為在某些情況下我們這樣做會更高效或者更合理。比如生活中的排隊現象,可以思考這樣幾個問題:我們為什麼要排隊?

不排隊會有什麼狀況發生?在所有的場合中我們都要排隊嗎?排隊只是為了能更高效的做某件事,在特定的情形下排隊會提高效率,但是並不是所有場合都需要排隊啊,比如"搶購商品",如果搶購商品還需要排隊的話,那就不能稱為搶購了。

所以說棧和佇列只是在某些場景下我們的人為規定的操作,這並不影響相關資料結構的靈活性,反而會使特定場景的效率更高。

最後給題主乙個建議,學習資料結構不能太死板,要靈活,我們在使用資料結構,而不是資料結構在支配我們。

為什麼分不清棧和佇列也能得到阿里的面試機會?

一地故鄉 回答的時候是16.1.10,再次編輯的時候是18.1.9,從前我也學過棧和佇列,然而全忘了。現在被考試逼的都能分清棧和佇列了,激動的老臉一紅!原回答題主呀!面試機會可以自己去爭取的呀,沒通知你就自己問呀!從你說的就感覺你沒有很大的動力和願望去阿里,你可以在面試的時候自己過去呀,膽子大些也是...

我們在深度學習中討論的線性和非線性到底是什麼?

Mr.Bruins 1 卷積是線性的本質就是 kx 2 線性運算就是乘加運算,就是kx b,在二維的表現就是一條直線非線性參考各種形狀的線,二次,三次,log,exp,啟用函式帶來的就是這種非線性,通過一段段的線性截斷去模擬非線性形狀,可以理解成積分,所有的線性線段的積分可以構成乙個非線性函式。所以...

自然吸氣發動機的線性是指什麼和什麼呈線性?

Vic 我先說下我開過的 不線性 的車。典型的就是老Golf7,在起步階段 油門輕踩了車不動。踩重就串。所以,不線性 可以理解為。車輛的輪上動力輸出沒有完全吻合使用者的動力輸出請求。這更多的是變速箱的問題。而不是發動機問題。可以說個栗子。豐田皇冠上的2.0T 8AT 渦輪增壓發動機 VS 同樣同樣的...