Python第十天：数据结构与面向对象编程笔记总结

1. 栈Stack1.1 栈的基本概念栈是一种**后进先出LIFO**的数据结构类似于餐厅洗盘子的过程栈顶允许进行插入和删除操作的一端栈底不允许进行插入和删除操作的一端空栈不包含任何元素的栈栈的主要特点只能在一端栈顶进行操作后进入的元素先被取出操作时间复杂度通常为 O(1)1.2 Python中的栈实现Python没有内置的栈类但可以通过列表list来模拟栈的操作# 创建一个空栈stack[]# 栈的基本操作# 1. 获取栈的长度lengthlen(stack)# 2. 进栈压栈操作stack.append(10)# 将10压入栈顶stack.append(20)stack.append(30)# 3. 出栈弹栈操作ifstack:# 判断栈是否为空top_elementstack.pop()# 弹出栈顶元素30print(f弹出的元素是:{top_element})# 4. 获取栈顶元素不弹出ifstack:peek_elementstack[-1]# 查看栈顶元素20print(f栈顶元素是:{peek_element})# 5. 判断栈是否为空ifnotstack:# 列表为空时被视为Falseprint(栈为空)else:print(栈不为空)1.3 栈的应用示例洗碗问题下面是一个模拟洗碗过程的栈应用实例# 题目模拟洗碗过程# 操作1洗一个盘子出栈# 操作2放入一个脏盘子入栈nint(input())# 初始的盘子数量plateslist(map(int,input().split()))# 初始的盘子栈mint(input())# 要执行的操作次数foriinrange(m):operationinput().split()optint(operation[0])ifopt1:# 洗盘子出栈ifplates:# 判断盘子栈是否为空cleaned_plateplates.pop()print(f洗了盘子:{cleaned_plate})elifopt2:# 放入脏盘子入栈plate_numberint(operation[1])plates.append(plate_number)print(f放入脏盘子:{plate_number})# 最终状态判断ifnotplates:print(All the dishes have been washed.)else:print(f还剩盘子:{plates[-1]})2. 队列Queue2.1 队列的基本概念队列是一种**先进先出FIFO**的数据结构类似于现实生活中的排队队头允许进行删除操作的一端出队队尾允许进行插入操作的一端入队队列的主要特点在队尾插入元素入队在队头删除元素出队先进入的元素先被取出2.2 Python中的队列实现Python提供了多种队列实现方式方式1使用列表模拟队列简单但不高效# 使用列表模拟队列queue[]# 入队操作queue.append(1)queue.append(2)queue.append(3)# 出队操作效率较低因为pop(0)需要移动所有元素ifqueue:front_elementqueue.pop(0)# 出队并返回队头元素print(f出队元素:{front_element})# 访问队头元素ifqueue:print(f队头元素:{queue[0]})# 获取队列长度print(f队列长度:{len(queue)})# 判断队列是否为空ifnotqueue:print(队列为空)方式2使用queue模块推荐用于多线程importqueue# 创建一个先进先出队列qqueue.Queue()# 入队操作q.put(1)q.put(2)q.put(3)# 出队操作itemq.get()# 出队并返回队列中的元素print(f出队元素:{item})# 输出 1# 判断队列是否为空ifq.empty():print(队列为空)else:print(f队列大小:{q.qsize()})方式3使用collections.deque高效的双端队列fromcollectionsimportdeque# 创建双端队列也可用作普通队列dqdeque()# 入队操作dq.append(1)# 从右侧入队dq.append(2)dq.append(3)# 出队操作ifdq:frontdq.popleft()# 从左侧出队print(f出队元素:{front})# 访问队头元素ifdq:print(f队头元素:{dq[0]})3. 面向对象编程OOP3.1 类的基本写法面向对象编程是Python的核心特性之一主要包括封装、继承、多态三大特性。# 类的基本结构class类名:# 类属性所有实例共享类属性共享值# 初始化方法构造函数def__init__(self,参数1,参数2):# 实例属性每个实例独有self.属性1参数1self.属性2参数2# 实例方法defmethod_1(self,参数):# 方法实现returnself.属性1参数# 类方法classmethoddef类方法名(cls):returncls.类属性# 静态方法staticmethoddef静态方法名():return静态方法# 创建类的实例instance1类名(值1,值2)# 调用类的方法resultinstance1.method_1(附加参数)3.2 封装Encapsulation封装是将对象的属性和方法包装在一起并隐藏内部实现细节。classCircle:def__init__(self,radius):# 使用双下划线开头表示私有属性self.__radiusradius# Getter方法获取半径defget_radius(self):returnself.__radius# Setter方法设置半径可以添加验证逻辑defset_radius(self,radius):ifradius0:self.__radiusradiuselse:print(半径必须大于0)# 计算面积defarea(self):return3.14159*self.__radius**2# 使用封装的类circleCircle(5)print(f半径:{circle.get_radius()})# 通过getter访问print(f面积:{circle.area()})circle.set_radius(10)# 通过setter修改print(f新半径:{circle.get_radius()})3.3 继承Inheritance继承允许一个类获取另一个类的属性和方法避免代码重复。# 父类基类classAnimal:def__init__(self,name):self.namenamedefspeak(self):return动物发出声音defeat(self):returnf{self.name}在吃东西# 子类派生类classDog(Animal):# Dog继承自Animaldef__init__(self,name,breed):# 调用父类的初始化方法super().__init__(name)self.breedbreed# 重写父类方法defspeak(self):return汪汪# 子类特有的方法deffetch(self):returnf{self.name}在接飞盘# 另一个子类classCat(Animal):defspeak(self):return喵喵# 使用继承dogDog(旺财,金毛)print(dog.eat())# 继承自父类的方法print(dog.speak())# 子类重写的方法print(dog.fetch())# 子类特有的方法catCat(咪咪)print(cat.speak())# 输出: 喵喵3.4 多态Polymorphism多态是指同一个方法在不同类中有不同的实现。classShape:defarea(self):pass# 抽象方法由子类实现classRectangle(Shape):def__init__(self,width,height):self.widthwidth self.heightheightdefarea(self):returnself.width*self.heightclassCircle(Shape):def__init__(self,radius):self.radiusradiusdefarea(self):return3.14159*self.radius**2# 多态演示不同对象调用相同方法名但执行不同的实现shapes[Rectangle(4,5),Circle(3)]forshapeinshapes:# 虽然都是调用area()方法但实际执行的是各自类的实现print(f面积:{shape.area()})4. 总结对比栈 vs 队列特性栈 (Stack)队列 (Queue)操作原则LIFO后进先出FIFO先进先出插入位置栈顶队尾删除位置栈顶队头主要操作push/popenqueue/dequeue典型应用函数调用栈、括号匹配、撤销操作消息队列、任务调度、广度优先搜索面向对象三大特性封装隐藏对象内部状态通过公共接口访问继承子类继承父类属性和方法实现代码复用多态同一接口在不同类中有不同实现实际应用建议栈适合需要撤销功能的场景如文本编辑器的撤销操作队列适合需要按顺序处理的场景如打印任务队列面向对象适合构建复杂系统提高代码的可维护性和复用性通过理解这些基本概念和代码示例可以更好地应用数据结构和面向对象思想解决实际问题。