python中基本數據結構（一）

1- 什麼是棧？

　　一個棧是一個項的有序集合。添加項和移除項都在同一端，這一端被稱為‘棧頂’。另一端被稱為‘棧底’。

　　棧使用的是後進先出原則即‘LIFO’原則，也就是說最新添加的項在移除時是第一個被移除的。在日常生活中有很多例子比如說在餐廳中有一堆餐盤，我們拿走的是最頂上的一個，排在我們後面的人將拿走下一個。

　　例如：有一個棧，棧內元素為（棧底——棧頂）1,2,3,4,5,6,7,8　　取出  5   的順序為

　　　　次數　　　　元素　　　　　　　　棧內元素　　　　　　

　　　　第一次　　取出棧頂元素  8 　　　1,2,3,4,5,6,7

　　　　第二次　　取出棧頂元素  7 　　　1,2,3,4,5,6

　　　　第三次　　取出棧頂元素  6 　　　1,2,3,4,5

　　　　第四次　　取出棧頂元素  5 　　　1,2,3,4

　　第四次取到了棧內元素 5  

2- 棧的基本操作

 1 class Stack():
 2     # 初始化棧
 3     def __init__(self):
 4         self.__items = []
 5 
 6     # 將新項添加到堆棧的頂部。它需要參數item並且沒有返回值。
 7     def Push(self,item):
 8         self.__items.append(item)
 9 
10     # 從棧頂刪除項它不需要參數,返回item,棧被修改。
11     def pop(self):
12         if self.__items == []:
13             return
14         return self.__items.pop()
15 
16     # 返回棧頂的項，不刪除它。它不需要參數。堆棧不被修改。
17     def peek(self):
18         if self.__items == []:
19             return
20         return self.__items[len(self.__items)-1]
21 
22     # 測試看棧是否為空。它不需要參數，返回一個布爾值。
23     def isEmpty(self):
24         return self.__items == []
25 
26     # 返回棧的項目數。它不需要參數，返回一個整數。
27     def size(self):
28         return len(self.__items)

棧方法：

• Stack()創建一個新的空棧。它不需要參數，並返回一個空棧。
• Push(item)將新項添加到堆棧的頂部。它需要參數 item 並且沒有返回值。
• pop()從棧頂刪除項目。它不需要參數,返回 item。棧被修改。
• peek()返回棧頂的項，不刪除它。它不需要參數。堆棧不被修改。
• isEmpty()測試看棧是否為空。它不需要參數，返回一個布爾值。
• size()返回棧的項目數。它不需要參數，返回一個整數。