1.列表/数组

列表是一种基本数据结构

• Python的列表存储元素的首地址，可以不区分元素的类型
• Python列表按下标查找，插入，删除元素，时间复杂度为O(1)

2.栈

栈是一个数据集合，可以理解为只能一端进行插入或删除操作的列表

• 进行入栈或出栈的一端称为栈顶
• 栈的基本操作：进栈push，出栈pop，取栈顶gettop

2.1栈的实现：列表

# 用列表实现栈
class Stack:def __init__(self):self.stack=[]def push(self,element):self.stack.append(element)def pop(self):return self.stack.pop()def gettop(self):if len(self.stack)>0:return self.stack[-1]else:return None# 字符串包含括号，判断括号是否成对出现
def brace_match(str):match = {'}':'{',']':'[',')':'('}stack = Stack()for s in str:# 字符属于左括号if s in {'{','[','('}:stack.push(s)else:# 栈顶:1）为空if stack.is_empty():return False# 栈顶：2）为右括号elif stack.gettop()==match[s]:stack.pop()# 栈顶：3）其他字符else:return Falseif stack.is_empty():return Trueelse:return False
print(brace_match("{}")) #True
print(brace_match("{[]()}")) #True
print(brace_match("{[]({)}")) #False

2.1栈的实现：链表

 # 待实现

3.队列

队列是一个数据集合，仅允许在队列的一端进行插入，另一段进行删除

• 进行插入的一端称为队尾，插入动作称为进队或入队
• 进行删除的一端称为队头，删除动作称为出队
• 先进先出First-in，First-out

3.1队列的实现：列表简单实现

使用front和rear指向的位置表示队头和队尾，入队rear加1，出队front加1，这样插入和删除的时间复杂度为O(1)。
问题1：：若干次入队出队后，front指向位置前面的空间是浪费的，不能使用也无法释放。

3.2队列的实现：环形队列

• 环形队列：当队尾指针等于Maxsize+1时，再进一个位置就自动到0
• 队空条件：rear==front
• 队满条件：(rear+1)%MaxSize==front
• 队首指针前进1：front==(front+1)%MaxSize
• 队尾指针前进1：rear==(rear+1)%MaxSize

 # 环形队列实现队列class Queue:def __init__(self,size=100):self.queue = [0 for _ in range(size)]self.size = sizeself.front = 0self.rear = 0def push(self,element):if not self.is_full():self.rear = (self.rear+1)%self.sizeself.queue[self.rear]=elementelse:raise IndexError("队满")# 返回出队后队首元素def pop(self):if not self.is_empty():self.front = (self.front+1)%self.sizereturn self.queue[self.front]else:raise IndexError("队空")def is_empty(self):return self.front==self.reardef is_full(self):return (self.rear+1)%self.size==self.front

3.3栈的实现：链表

 # 待实现

3.4Python队列内置模块

• 使用方法：from collections import deque
• 创建队列：queue=deque()， 第一个参数设置列表，表示创建一个有数的队列；第二个参数，表示队列长度。当队列满了又进队，默认第一个出队
• 进队：append()
• 出队：popleft()
• 双向队列队首进队：appendleft()
• 双向队列队尾出队：pop()
• 队空时出队抛出异常IndexError

# test.txt文件内容
first line
second line
third line
forth line
fifth line
sixth line
seventh line
eighth line
nineth line
texth linefrom collections import deque
def tail(n):with open('test.txt','r') as f:q = deque(f,n)return q
#text.txt文件最后5行内容
for line in tail(5):print(line,end='')