python基本数据结构类型--初识栈

dlnb526

MOOC课程 《数据结构与算法》（北大地空）笔记
by dlnb526
2020.3

预备知识：线性结构（线性表）

• 前驱和后继
  

线性结构的特点就在于其线性，也就是说整个结构里面的元素都只有一个前驱和一个后继（除了开头和结尾的元素），就像是一串糖葫芦或者列车一样。
当我们向线性结构中添加一个项目时，他会放在之前的项和后来的项之间。

栈
什么是栈

• 栈是线性结构
• 栈是一个项的有序集合
• 栈遵循LIFO原则
  

LIFO原则（Last in, First out.后进先出）。栈的添加项和移除项都会发生在同一端，另一端我们不妨称之为‘底’。这样每当添加一个项，原本就靠近‘底’的元素就会更加被压在底下，因此它在栈中存储的时间会更长。

栈的抽象数据类型

• Stack(): 创建一个新的空栈，它不需要参数并返回一个空栈。
• push(item): 将一个新项目添加到堆栈的顶部。
• pop(): 从栈顶删除项目，不需要参数，返回所删除的item，进行操作后栈会被修改
• peek(): 返回栈顶的项，不删除。
• isEmpty(): 测试栈是否为空，返回一个布尔值
• size(): 返回栈的项目数
  

接下来我们通过python来构建上面的栈的结构。

构建栈

1. # Bradley N. Miller, David L. Ranum
   
2. # Introduction to Data Structures and Algorithms in Python
   
3. # Copyright 2005
   
4. #
   
5. #stack.py
   
6. 
   
7. class Stack:
   
8.     def __init__(self):
   
9.         self.items = []
   
10. 
    
11.     def isEmpty(self):
    
12.         return self.items == []
    
13. 
    
14.     def push(self, item):
    
15.         self.items.append(item)
    
16. 
    
17.     def pop(self):
    
18.         return self.items.pop()
    
19. 
    
20.     def peek(self):
    
21.         return self.items[len(self.items)-1]
    
22. 
    
23.     def size(self):
    
24.         return len(self.items)

复制代码

通过上面的方法就完成了栈的构建。

复杂度分析
对栈进行操作，其实都是相当于直接对列表的尾端进行操作，因此我们可以知道其时间复杂度如下：

操作	复杂度
push(item)	O(1)
pop()	O(1)
peek()	O(1)
isEmpty()	O(1)
size()	O(1)

之后
下次的内容将是栈的两个应用举例~

评分！评分！评分！~

永恒的蓝色梦想

1. class Stack(list):
   
2. 
   
3.     def isEmpty(self):
   
4.         return not self
   
5. 
   
6.     def push(self, item):
   
7.         self.append(item)
   
8. 
   
9.     def pop(self):
   
10.         return list.pop(self)
    
11. 
    
12.     def peek(self):
    
13.         return self[-1]
    
14. 
    
15.     def size(self):
    
16.         return self.__len__()

复制代码

直接继承List不也很好吗

dlnb526

永恒的蓝色梦想 发表于 2020-3-28 21:30
直接继承List不也很好吗

额这个我放的是  pythonds 模块中栈（stack)的源代码。pythonds 中有各种数据结构的实现~我以后都直接用这里的电池~