持续更新中。。。。学到哪总结到哪

0. 介绍

没什么说的。。。。当目录用吧。。。

1. python内置数据结构

四件套很基础，大致过一下

1.1 列表

这个。。。就是增删改查。大致复习一下，以后python数据结构和算法基本上都是用列表实现

# 创建列表
li = []
# 从末尾增加数据
li.append(1)
# 从自定义位置增加数据
li.insert(0, 2)
# 修改数据
li[0]= 3
# 从末尾删除数据
li.pop()
# 从指定位置删除数据
li.pop(0)
# 获取长度
len(li)
# 遍历列表
for i in range(len(li)):
    print(i)

1.2 元组

# 创建元组
tup_single = (50,)

1.3 字典

# 创建字典
dict1 = {"age": 18}
# 添加&修改元素
dict1['age'] = 31 
dict1['name'] = 'xujie'
# 删除元素
del dict1['city']
name = dict1.pop('name')
# 获取键
dict1.keys()
# 获取值
dict1.values()
# 获取键值对
dict1.items()
# 字典赋值
dict1.update({"age":19})
# 清空
dict1.clear()

1.4 集合

# 创建集合
set1 = {1, 2, 3, 4}
set2 = set([1, 2, 3, 4])
# 添加元素
set1.add(5)
# 移除元素
set1.remove(3)
# 随机弹出元素
set_element = set1.pop()
# 清空集合
set1.clear()

2. 线性表

2.1 字符串

字符串是一种线性表，也是python内置数据结构之一，因其性质较多，故规划进线性表内

# 创建
# 单行
string1 = 'hello world'
# 多行
string2 = '''
1
2
3
'''

# 拼接
string2 = string1 + string1
# 重复
string2 = "hello "*3
# 索引
string2 = string1[0]

# 转小写
string1.lower()
# 转大写
string1.upper()
# 去除两端空白
string1.strip()
# 替换内容
string1.replace("h", "H")
# 查找
string1.find("l")
# 拆分
stirng1.split(" ")
# 连接
'...'.join(string1)
# 判断开头
string1.startswith("h")
# 判断结尾
string1.endswitch("d")

# 编码
string1 = string1.encode('utf-8')
# 解码
string1 = string1.decode('utf-8')

# 迭代
for i in string1:
	print(i)

2.2 python栈的实现

栈是一种先进后出的数据结构，可以使用列表append方法实现将元素仅能从列表尾部插入数据(压栈)，并且不能从列表其他位置压入栈，使用列表的pop方法实现仅能从列表尾部(栈顶)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Stack:
	"""栈类"""
	def __init__(self):
		self._li = []
		
	def push(self, item):
		"""进栈方法"""
		self._li.append(item)
	
	def pop(self):
		"""出栈方法"""
		self._li.pop()
	
	def travel(self):
		"""遍历方法"""
		_sum = []
		for i in self._li:
			_sum.append(i)
		return _sum	

2.3 python队列的实现

队列是一种先进先出的数据结构

2.3.1 单调队列

可以使用列表append方法实现将元素仅能从列表尾部插入数据(入队)，并且不能从列表其他位置入队，使用列表的pop(0)方法实现仅能从列表头部(队头)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Queue:
	"""单调队列类"""
	def __init__(self):
		self._li = []
	
	def push(self, item):
		"""入队列"""
		self._li.append(item)
	
	def pop(self, item):
		"""出队列"""
		self._li.pop(0)
	
	def travel(self):
		"""遍历队列"""
		_num = []
		for i in range(len(self._li)):
			_num.append(i)
		return _num

2.3.2 双端队列

可以从队头和队尾任意一端入队，也可以从队头和队尾任意一端出队
可以使用列表append和insert(0, item)方法实现将元素从列表尾部(头部)插入数据(入队)，并且不能从列表其他位置入队，使用列表的pop()和pop(0)方法实现仅能从列表头部(尾部)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Dequeue:
	"""双端队列类"""
	def __init__(self):
		self._li = []
	
	def front_push(self, item):
		"""队头插入数据"""
		self._li.insert(0, item)

	def back_push(self, item):
		"""队尾插入数据"""
		self._li.append(item)

	def front_pop(self):
		"""队头弹出数据"""
		self._li.pop(0)

	def back_pop(self):
		"""队尾弹出数据"""
		self._li.pop()

	def travel(self):
		"""遍历队列"""
		_num = []
		for i in range(len(self._li)):
			_num.append(i)
		return _num

2.3.3 循环队列

2.3.3.1 什么是循环队列？

循环队列是一种利用数组（或固定长度存储结构）实现的队列，队列的头尾指针在到达数组末尾时会“环绕”到数组的起始位置，实现“首尾相连”的效果。这样可以充分利用数组空间，避免“假满”问题。

2.3.3.2 为什么需要循环队列？

在普通队列中，出队（dequeue）会导致前端空间释放，但队列尾部可能未能回收前端空间，造成空间浪费。而循环队列通过环绕利用空间，实现队列的空间最大化。

2.3.3.3 核心原理

使用一个固定长度的数组（或列表）存放元素。
使用两个指针（或索引）：front（队头指针） 和 rear（队尾指针）。
当队列满时，(rear + 1) % size == front。
当队列空时，front == rear。

class CircleQueue:
	def __init__(self, size=100):
	# 我定义100个长度的列表，可自定义
	self.size = size
	# 用0站位，不然被回收掉了，可随便更改站位字符
	self.queue = [0 for _ in range(size)]
	# 队头指针
	self.front = 0
	# 队尾指针
	self.rear = 0

	def is_empty(self):
		"""队列判空"""
		# 如果队头等于队尾，证明队中没有元素
		return self.front == self.rear
	
	def is_full(self):
		"""队列判满"""
		# 如果队尾的下一个元素就是队头，则证明队满了（预留了一个判定位，见图）
		return (self.rear + 1) % self.size == self.front

	def push(self, item):
		"""入队方法"""
		# 如果队没满，可以执行入队
		if not self.is_full():
			# 将队尾指针后移一个（取模操作是因为要循环，不然会一直增下去，环不起来）
			self.rear = (self.rear+1)%self.size
			# 添加元素
			self.queue[self.rear] = item
		# 如果队满了，肯定入不了队了，弹出异常
		raise IndexError('circle queue is full')

	def pop(self):
		"""出队方法"""
		# 如果队里还有元素，可执行弹出操作
		if not self.is_empty():
			# 将队头指针后移一个（取模操作是因为要循环，不然会一直增下去，环不起来）
			self.front = (self.front + 1) % self.size
			# 弹出元素
			return selfqueue[self.front]

# 其他方法可自定义，比如说遍历、打印队首（队尾）元素等等

注意：弹出元素方法千万不能 .pop()，不然pop掉的那一个列表位没有元素占位，会被回收掉，造成列表长度-1，环形队列设定好size大小后，在操作中不能随意改变size，也就是列表长度大小