❶ python堆和棧的區別有哪些
堆（Heap）與棧（Stack）是開發人員必須面對的兩個概念，在理解這兩個概念時，需要放到具體的場景下，因為不同場景下，堆與棧代表不同的含義。一般情況下，有兩層含義：
（1）程序內存布局場景下，堆與棧表示的是兩種內存管理方式；
（2）數據結構場景下，堆與棧表示兩種常用的數據結構。
相關推薦：《Python教程》
堆與棧實際上是操作系統對進程佔用的內存空間的兩種管理方式，主要有如下幾種區別：
（1）管理方式不同。棧由操作系統自動分配釋放，無需我們手動控制；堆的申請和釋放工作由程序員控制，容易產生內存泄漏；
（2）空間大小不同。每個進程擁有的棧的大小要遠遠小於堆的大小。理論上，程序員可申請的堆大小為虛擬內存的大小，進程棧的大小 64bits 的 Windows 默認 1MB，64bits 的 Linux 默認 10MB；
（3）生長方向不同。堆的生長方向向上，內存地址由低到高；棧的生長方向向下，內存地址由高到低。
（4）分配方式不同。堆都是動態分配的，沒有靜態分配的堆。棧有2種分配方式：靜態分配和動態分配。靜態分配是由操作系統完成的，比如局部變數的分配。動態分配由alloca函數進行分配，但是棧的動態分配和堆是不同的，他的動態分配是由操作系統進行釋放，無需我們手工實現。
（5）分配效率不同。棧由操作系統自動分配，會在硬體層級對棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執行，這就決定了棧的效率比較高。堆則是由C/C++提供的庫函數或運算符來完成申請與管理，實現機制較為復雜，頻繁的內存申請容易產生內存碎片。顯然，堆的效率比棧要低得多。
（6）存放內容不同。棧存放的內容，函數返回地址、相關參數、局部變數和寄存器內容等。當主函數調用另外一個函數的時候，要對當前函數執行斷點進行保存，需要使用棧來實現，首先入棧的是主函數下一條語句的地址，即擴展指針寄存器的內容（EIP），然後是當前棧幀的底部地址，即擴展基址指針寄存器內容（EBP），再然後是被調函數的實參等，一般情況下是按照從右向左的順序入棧，之後是被調函數的局部變數，注意靜態變數是存放在數據段或者BSS段，是不入棧的。出棧的順序正好相反，最終棧頂指向主函數下一條語句的地址，主程序又從該地址開始執行。堆，一般情況堆頂使用一個位元組的空間來存放堆的大小，而堆中具體存放內容是由程序員來填充的。
從以上可以看到，堆和棧相比，由於大量malloc()/free()或new/delete的使用，容易造成大量的內存碎片，並且可能引發用戶態和核心態的切換，效率較低。棧相比於堆，在程序中應用較為廣泛，最常見的是函數的調用過程由棧來實現，函數返回地址、EBP、實參和局部變數都採用棧的方式存放。雖然棧有眾多的好處，但是由於和堆相比不是那麼靈活，有時候分配大量的內存空間，主要還是用堆。
無論是堆還是棧，在內存使用時都要防止非法越界，越界導致的非法內存訪問可能會摧毀程序的堆、棧數據，輕則導致程序運行處於不確定狀態，獲取不到預期結果，重則導致程序異常崩潰，這些都是我們編程時與內存打交道時應該注意的問題。
❷ python-033-實現棧-使用鏈表實現-提高時間復雜度
棧在我們之前的文章中就說陵前明過了，想了解的去看一下030即可。
之前我們實現的棧穗汪高，演算法時間復雜度在攤銷的情況下，是O(1)，其底層是python的列表，是一種動態數組，在內存中是一個固定長度的數組，是無法改變大小的，只有重新換一個更大的數組來裝新的數據猜尺。雖然實現起來非常簡單，但是並不夠完美。
在我們最開始的幾篇文章中，很詳細的介紹了鏈表的各種使用方式。之前實現鏈表時，只聲明了節點對象，但是我們在程序的使用中應該把鏈表作為一個整體，作為一個對象來使用，這樣封裝性更好。
今天就不寫這個鏈表了，我們利用在棧類中定義一個 嵌套類 來做為鏈表的節點對象，因為創建節點的操作非常多，所以我們用 slots 來聲明節點的兩個成員變數，來減少內存的使用，提高效率。
鏈表是一種可以隨時改變的數據結構。我們可以隨時改變他的結構。
實現如下：
這次實現的棧的每一個方法操作，其時間復雜度都為O(1)，不需要攤銷。這與用數組實現的棧形成了對比。
鏈表實現的更快，明天用鏈表實現隊列。