linux資料結構(堆、棧、佇列)
1.堆
·堆中某個節點的值總是不大於或不小於其父節點的值;
·堆總是一棵完全二叉樹。
1)堆是在程式執行時動態分配記憶體,一般是申請/給予的過程。而不是在程式編譯時,申請某個大小的記憶體空間。
2)先進後出
3) 二級快取。一般由程式設計師分配釋放, 若程式設計師不釋放,程式結束時可能由OS回收,分配方式倒是類似於連結串列
2.棧
1)棧只是指一種使用堆的方法,棧(stack)又名堆疊,它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂,相對地,把另一端稱為棧底。
2)棧就是一個桶,先進後出。
3)一級快取,呼叫完立即釋放。
3.佇列
1)建立順序佇列結構必須為其靜態分配或動態申請一片連續的 儲存空間,並設定兩個指標進行管理。一個是隊頭指標front,它指向隊頭元素;另一個是隊尾指標rear,它指向下一個入隊元素的儲存位置。
2)動態建立,動態釋放。因而也不存在溢位等問題。由於連結串列由結構體間接而成,遍歷也方便。
3)沒有底的桶,先進先出。
堆、棧、佇列之間的區別是?
①堆是在程式執行時,而不是在程式編譯時,申請某個大小的記憶體空間。即動態分配記憶體,對其訪問和對一般記憶體的訪問沒有區別。
②棧就是一個桶,後放進去的先拿出來,它下面本來有的東西要等它出來之後才能出來。(後進先出)
③佇列只能在隊頭做刪除操作,在隊尾做插入操作.而棧只能在棧頂做插入和刪除操作。(先進先出)
棧只是指一種使用堆的方法。