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()返回栈的项目数。它不需要参数，返回一个整数。