python複雜數據結構之棧（棧是非線性數據結構）

本文目錄一覽：

• 1、Python數據結構與算法-利用列表實現棧
• 2、Python 之“棧為何物”
• 3、python中的堆棧什麼意思
• 4、python中的數據結構分析？
• 5、python堆和棧的區別有哪些
• 6、PYTHON的數據結構和算法介紹

Python數據結構與算法-利用列表實現棧

概念：

棧：

名稱的由來：這個名字來源於自動售貨機中用彈簧頂住的一堆盤子的隱喻。

概念：這裡提到的棧是一種抽象的數據結構

，而非空間內存分配處涉及的空間存儲的概念。但是大同小異，原理還是來自於對棧空間的理解。這裡的棧是有一系列對象組成的一個集合，這些對象的插入和刪除操作遵循後進先出（LIFO）原則。用戶可以在任意時刻向棧中插入一個對象，但只能取得或者刪除最後一個插入的對象（即所謂的棧頂）。

目的：通過列表實現棧

有些同學可能認為，是不是還有其他操作沒有完成，為什麼不能在中間插入或者其他操作，因為棧不具備這些功能，所以實現的都是棧的常規功能。

利用棧實現數據的逆置

由於LIFO協議的限制，棧可以用作一種通用的工具，用於實現一個數據序列的逆置，這一思想可以用於很多方面，例如以降序

的方式顯示一個數據集，我們可以通過先逐行讀取數據，然後壓如一個棧中，在按照從棧中彈出的順序來寫入。這個方法的實現過程如下：

Python 之“棧為何物”

究竟棧為何物

棧是一種 線性數據結構 ，用 先進後出 或者是 後進先出 的方式存儲數據，棧中數據的插入刪除操作都是在棧頂端進行。

棧是一種特殊的列表，棧內的元素只能通過一端進行訪問，這一端為棧頂。

Python 如何實現棧

使用內置數據結構 List 可以用來實現棧；

使用 append() 向棧頂添加元素；

使用 pop() 可以以後進先出的順序刪除元素；

Python 實戰代碼

python中的堆棧什麼意思

堆棧是一種執行“後進先出”算法的數據結構。

設想有一個直徑不大、一端開口一端封閉的竹筒。有若干個寫有編號的小球，小球的直徑比竹筒的直徑略小。現在把不同編號的小球放到

竹筒裡面，可以發現一種規律：先放進去的小球只能後拿出來，反之，後放進去的小球能夠先拿出來。所以“先進後出”就是這種結構的

特點。

堆棧是計算機中最常用的一種數據結構，比如函數的調用在計算機中是用堆棧實現的。 堆棧可以用數組存儲，也可以用以後會介紹的鏈

表存儲。

堆棧就是這樣一種數據結構。它是在內存中開闢一個存儲區域，數據一個一個順序地存入（也就是“壓入——push”）這個區域之中。

有一個地址指針總指向最後一個壓入堆棧的數據所在的數據單元，存放這個地址指針的寄存器就叫做堆棧指示器。開始放入數據的單元叫

做“棧底”。數據一個一個地存入，這個過程叫做“壓棧”。在壓棧的過程中，每有一個數據壓入堆棧，就放在和前一個單元相連的後面

一個單元中，堆棧指示器中的地址自動加1。讀取這些數據時，按照堆棧指示器中的地址讀取數據，堆棧指示器中的地址數自動減 1。這

個過程叫做“彈出pop”。如此就實現了後進先出的原則。

推薦學習《python教程》。

python中的數據結構分析？

1.Python數據結構篇

數據結構篇主要是閱讀[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [該網址鏈接可能會比較慢]時寫下的閱讀記錄，當然，也結合了部分[算法導論](Introduction to Algorithms)

中的內容，此外還有不少wikipedia上的內容，所以內容比較多，可能有點雜亂。這部分主要是介紹了如何使用Python實現常用的一些數據結構，例

如堆棧、隊列、二叉樹等等，也有Python內置的數據結構性能的分析，同時還包括了搜索和排序(在算法設計篇中會有更加詳細的介紹)的簡單總結。每篇文

章都有實現代碼，內容比較多，簡單算法一般是大致介紹下思想及算法流程，複雜的算法會給出各種圖示和代碼實現詳細介紹。

**這一部分是下

面算法設計篇的前篇，如果數據結構還不錯的可以直接看算法設計篇，遇到問題可以回來看數據結構篇中的某個具體內容充電一下，我個人認為直接讀算法設計篇比

較好，因為大家時間也都比較寶貴，如果你會來讀這些文章說明你肯定有一定基礎了，後面的算法設計篇中更多的是思想，這裡更多的是代碼而已，嘿嘿。**

(1)[搜索](Python Data Structures)

簡述順序查找和二分查找，詳述Hash查找(hash函數的設計以及如何避免衝突)

(2)[排序](Python Data Structures)

簡述各種排序算法的思想以及它的圖示和實現

(3)[數據結構](Python Data Structures)

簡述Python內置數據結構的性能分析和實現常用的數據結構：棧、隊列和二叉堆

(4)[樹總結](Python Data Structures)

簡述二叉樹，詳述二叉搜索樹和AVL樹的思想和實現

2.Python算法設計篇

算法設計篇主要是閱讀[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**點擊鏈接可進入Springer免費下載原書電子版**]之後寫下的讀書總結，原書大部分內容結合了經典書籍[算法導論](Introduction to Algorithms)，

內容更加細緻深入，主要是介紹了各種常用的算法設計思想，以及如何使用Python高效巧妙地實現這些算法，這裡有別於前面的數據結構篇，部分算法例如排

序就不會詳細介紹它的實現細節，而是側重於它內在的算法思想。這部分使用了一些與數據結構有關的第三方模塊，因為這篇的重點是算法的思想以及實現，所以並

沒有去重新實現每個數據結構，但是在介紹算法的同時會分析Python內置數據結構以及第三方數據結構模塊的優缺點，也就意味着該篇比前面都要難不少，但

是我想我的介紹應該還算簡單明了，因為我用的都是比較樸實的語言，並沒有像算法導論一樣列出一堆性質和定理，主要是對着某個問題一步步思考然後算法就出來

了，嘿嘿，除此之外，裡面還有很多關於python開發的內容，精彩真的不容錯過！

這裡每篇文章都有實現代碼，但是代碼我一般都不會分

析，更多地是分析算法思想，所以內容都比較多，即便如此也沒有包括原書對應章節的所有內容，因為內容實在太豐富了，所以我只是選擇經典的算法實例來介紹算

法核心思想，除此之外，還有不少內容是原書沒有的，部分是來自算法導論，部分是來自我自己的感悟，嘻嘻。該篇對於大神們來說是小菜，請一笑而過，對於菜鳥

們來說可能有點難啃，所以最適合的是和我水平差不多的，對各個算法都有所了解但是理解還不算深刻的半桶水的程序猿，嘿嘿。

本篇的順序按照原書[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章節來安排的(章節標題部分相同部分不同喲)，為了節省時間以及保持原著的原滋原味，部分內容(一般是比較難以翻譯和理解的內容)直接摘自原著英文內容。

**1.

你也許覺得很多內容你都知道嘛，沒有看的必要，其實如果是我的話我也會這麼想，但是如果只是歸納一個算法有哪些步驟，那這個總結也就沒有意義了，我覺得這

個總結的亮點在於想辦法說清楚一個算法是怎麼想出來的，有哪些需要注意的，如何進行優化的等等，採用問答式的方式讓讀者和我一起來想出某個問題的解，每篇

文章之後都還有一兩道小題練手喲**

**2.你也許還會說算法導論不是既權威又全面么，基本上每個算法都還有詳細的證明呢，讀算法導論豈

不更好些，當然，你如果想讀算法導論的話我不攔着你，讀完了感覺自己整個人都不好了別怪小弟沒有提醒你喲，嘻嘻嘻，左一個性質右一個定理實在不適合算法科

普的啦，沒有多少人能夠堅持讀完的。但是碼農與蛇的故事內容不多喲，呵呵呵**

**3.如果你細讀本系列的話我保證你會有不少收穫的，需要看算法導論哪個部分的地方我會給出提示的，嘿嘿。溫馨提示，前面三節內容都是介紹基礎知識，所以精彩內容從第4節開始喲，么么噠 O(∩_∩)O~**

(1)[Python Algorithms – C1 Introduction](Python Algorithms)

本節主要是對原書中的內容做些簡單介紹，說明算法的重要性以及各章節的內容概要。

(2)[Python Algorithms – C2 The basics](Python Algorithms)

**本節主要介紹了三個內容：算法漸近運行時間的表示方法、六條算法性能評估的經驗以及Python中樹和圖的實現方式。**

(3)[Python Algorithms – C3 Counting 101](Python Algorithms)

原書主要介紹了一些基礎數學，例如排列組合以及遞歸循環等，但是本節只重點介紹計算算法的運行時間的三種方法

(4)[Python Algorithms – C4 Induction and Recursion and Reduction](Python Algorithms)

**本節主要介紹算法設計的三個核心知識：Induction(推導)、Recursion(遞歸)和Reduction(規約)，這是原書的重點和難點部分**

(5)[Python Algorithms – C5 Traversal](Python Algorithms)

**本節主要介紹圖的遍歷算法BFS和DFS，以及對拓撲排序的另一種解法和尋找圖的(強)連通分量的算法**

(6)[Python Algorithms – C6 Divide and Combine and Conquer](Python Algorithms)

**本節主要介紹分治法策略，提到了樹形問題的平衡性以及基於分治策略的排序算法**

(7)[Python Algorithms – C7 Greedy](Python Algorithms)

**本節主要通過幾個例子來介紹貪心策略，主要包括背包問題、哈夫曼編碼和最小生成樹等等**

(8)[Python Algorithms – C8 Dynamic Programming](Python Algorithms)

**本節主要結合一些經典的動規問題介紹動態規劃的備忘錄法和迭代法這兩種實現方式，並對這兩種方式進行對比**

(9)[Python Algorithms – C9 Graphs](Python Algorithms)

**本節主要介紹圖算法中的各種最短路徑算法，從不同的角度揭示它們的內核以及它們的異同**

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的數據結構和算法介紹

當你聽到數據結構時，你會想到什麼？

數據結構是根據類型組織和分組數據的容器。它們基於可變性和順序而不同。可變性是指創建後改變對象的能力。我們有兩種類型的數據結構，內置數據結構和用戶定義的數據結構。

什麼是數據算法-是由計算機執行的一系列步驟，接受輸入並將其轉換為目標輸出。

列表是用方括號定義的，包含用逗號分隔的數據。該列表是可變的和有序的。它可以包含不同數據類型的混合。

months=[‘january’,’february’,’march’,’april’,’may’,’june’,’july’,’august’,’september’,’october’,’november’,’december’]

print(months[0])#print the element with index 0

print(months[0:7])#all the elements from index 0 to 6

months[0]=’birthday #exchange the value in index 0 with the word birthday

print(months)

元組是另一種容器。它是不可變有序元素序列的數據類型。不可變的，因為你不能從元組中添加和刪除元素，或者就地排序。

length, width, height =9,3,1 #We can assign multiple variables in one shot

print(“The dimensions are {} * {} * {}”.format(length, width, height))

一組

集合是唯一元素的可變且無序的集合。它可以讓我們快速地從列表中刪除重複項。

numbers=[1,2,3,4,6,3,3]

unique_nums = set(numbers)

print(unique_nums)

models ={‘declan’,’gift’,’jabali’,’viola’,’kinya’,’nick’,betty’ }

print(‘davis’ in models)#check if there is turner in the set models

models.add(‘davis’)

print(model.pop())remove the last item#

字典

字典是可變和無序的數據結構。它允許存儲一對項目(即鍵和值)

下面的例子顯示了將容器包含到其他容器中來創建複合數據結構的可能性。

* 用戶定義的數據結構*

使用數組的堆棧堆棧是一種線性數據結構，其中元素按順序排列。它遵循L.I.F.O的機制，意思是後進先出。因此，最後插入的元素將作為第一個元素被刪除。這些操作是:

溢出情況——當我們試圖在一個已經有最大元素的堆棧中再放一個元素時，就會出現這種情況。

下溢情況——當我們試圖從一個空堆棧中刪除一個元素時，就會出現這種情況。

隊列是一種線性數據結構，其中的元素按順序排列。它遵循先進先出的F.I.F.O機制。

描述隊列特徵的方面

兩端:

前端-指向起始元素。

指向最後一個元素。

有兩種操作:

樹用於定義層次結構。它從根節點開始，再往下，最後的節點稱為子節點。

鏈表

它是具有一系列連接節點的線性數據。每個節點存儲數據並顯示到下一個節點的路由。它們用來實現撤銷功能和動態內存分配。

圖表

這是一種數據結構，它收集了具有連接到其他節點的數據的節點。

它包括:

算法

在算法方面，我不會講得太深，只是陳述方法和類型:

原文：