Python數據結構——棧

evin2016 發布于2019-07-31 10:49 / 1935人閱讀

摘要：棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱為棧頂。棧被稱為一種后入先出，的數據結構。對棧的兩種主要操作是將一個元素壓入棧和將一個元素彈出棧。入棧使用方法，出棧使用方法。方法則只返回棧頂元素，而不刪除它。

棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱為棧頂。咖啡廳內的一摞盤子是現實世界中常見的棧的例子。只能從最上面取盤子，盤子洗凈后，也只能摞在這一摞盤子的最上面。棧被稱為一種后入先出（LIFO，last-in-first-out）的數據結構。

由于棧具有后入先出的特點，所以任何不在棧頂的元素都無法訪問。為了得到棧底的元素，必須先拿掉上面的元素。

對棧的兩種主要操作是將一個元素壓入棧和將一個元素彈出棧。入棧使用push()方法，出棧使用pop()方法。下圖演示了入棧和出棧的過程。

另一個常用的操作是預覽棧頂的元素。pop()方法雖然可以訪問棧頂的元素，但是調用該方法后，棧頂元素也從棧中被永久性地刪除了。peek()方法則只返回棧頂元素，而不刪除它。

為了記錄棧頂元素的位置，同時也為了標記哪里可以加入新元素，我們使用變量top，當向棧內壓入元素時，該變量增大；從棧內彈出元素時，該變量減小。

push()、pop()和peek()是棧的3個主要方法，但是棧還有其他方法和屬性。

stack通常的操作：

Stack()    建立一個空的棧對象
push()     把一個元素添加到棧的最頂層
pop()      刪除棧最頂層的元素，并返回這個元素
peek()     返回最頂層的元素，并不刪除它
isEmpty()  判斷棧是否為空
size()     返回棧中元素的個數

簡單案例以及操作結果：

Stack Operation	Stack Contents	Return Value
s.isEmpty()	[]	True
s.push(4)	[4]
s.push("dog")	[4,"dog"]
s.peek()	[4,"dog"]	"dog"
s.push(True)	[4,"dog",True]
s.size()	[4,"dog",True]	3
s.isEmpty()	[4,"dog",True]	False
s.push(8.4)	[4,"dog",True,8.4]
s.pop()	[4,"dog",True]	8.4
s.pop()	[4,"dog"]	True
s.size()	[4,"dog"]	2

這里使用python的list對象模擬棧的實現：

class Stack: 
    """模擬棧""" 
    def __init__(self): 
        self.items = [] 

    def isEmpty(self): 
        return len(self.items)==0  

    def push(self, item): 
        self.items.append(item) 

    def pop(self): 
        return self.items.pop()  

    def peek(self): 
        if not self.isEmpty(): 
            return self.items[len(self.items)-1] 

    def size(self): 
        return len(self.items)

創建一個棧對象，并加入操作方法：

s=Stack() 
print(s.isEmpty()) 
s.push(4) 
s.push("dog") 
print(s.peek()) 
s.push(True) 
print(s.size()) 
print(s.isEmpty()) 
s.push(8.4) 
print(s.pop()) 
print(s.pop()) 
print(s.size())

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44179.html

線性結構隊列與棧

摘要：線性結構隊列與棧棧棧是一種遵循先進后出原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。將字符串的每個字符按順序亞入棧。線性結構隊列與棧棧棧(Stack)是一種遵循先進后出(LIFO)原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。棧的操作 ...

Turbo 2019-07-31 11:13 評論0 收藏0
線性結構隊列與棧

摘要：線性結構隊列與棧棧棧是一種遵循先進后出原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。將字符串的每個字符按順序亞入棧。線性結構隊列與棧棧棧(Stack)是一種遵循先進后出(LIFO)原則的有序列表，新添加或待刪除的元素都保存在棧的一端，這一端被稱作為棧頂，另一端被稱作為棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。棧的操作 ...

Turbo 2019-08-23 12:23 評論0 收藏0
Python全棧之路系列之列表數據類型

摘要：列表同字符串一樣都是有序的，因為他們都可以通過切片和索引進行數據訪問，且列表的的是可變的。列表(list)同字符串一樣都是有序的，因為他們都可以通過切片和索引進行數據訪問，且列表的的是可變的。創建列表的幾種方法第一種 name_list = [Python, PHP, JAVA] 第二種 name_list ＝ list([Python, PHP, JAVA]) 創建一個空列表 ...

琛ｈ。 2019-07-25 11:19 評論0 收藏0
python入門

摘要：零預備知識字符編碼計算機只能處理數字，所以為文本需要轉化為數字才能被計算機處理，計算機里八個比特作為一個字節，這是數據的存儲基礎單位。零、預備知識 0.1 字符編碼計算機只能處理數字，所以為文本需要轉化為數字才能被計算機處理，計算機里八個比特（bit）作為一個字節(byte)，這是數據的存儲基礎單位。計算機為了處理文本，有以下三種編碼方式： ASCII碼：只有大小寫英文字母，數字...

xeblog 2019-07-30 17:59 評論0 收藏0
《JavaScript快速全棧開發》作者Azat Mardanov：現在是擁抱Node技術棧的最佳時

摘要：長期以來，他都是和等機構的講師，其技術課程獲得一致好評。但是，如果讓我預測的話，我認為未來是很光明的，而現在就是擁抱技術棧的最佳時機。所以在瀏覽器和服務器之間代碼不需要上下文切換。如果沒有上下文切換，那么生產力也會更高。非商業轉載請注明作譯者、出處，并保留本文的原始鏈接：http://www.ituring.com.cn/article/195742 Azat Mardan...

Rango 2019-08-21 10:28 評論0 收藏0