Python 线性数据结构详解文件信息文件名: 01_线性数据结构.py开发思路和开发过程:首先介绍数组(List)的基本操作然后演示栈(Stack)的实现和应用接着展示队列(Queue)的实现和应用最后介绍双端队列(Deque)的使用代码功能: 演示线性数据结构的实现和使用包括数组、栈、队列和双端队列。代码实现#!/usr/bin/env python3# -*- coding: utf-8 -*- 文件名: 01_线性数据结构.py 开发思路和开发过程: 1. 首先介绍数组(List)的基本操作 2. 然后演示栈(Stack)的实现和应用 3. 接着展示队列(Queue)的实现和应用 4. 最后介绍双端队列(Deque)的使用 代码功能: 演示线性数据结构的实现和使用包括数组、栈、队列和双端队列。 print( 线性数据结构详解 \n)# 1. 数组(List)print(1. 数组(List):)# 创建数组arr[1,2,3,4,5]print(f创建数组:{arr})# 访问元素print(f访问第一个元素 arr[0]:{arr[0]})print(f访问最后一个元素 arr[-1]:{arr[-1]})# 修改元素arr[2]10print(f修改索引2的元素为10:{arr})# 添加元素arr.append(6)# 末尾添加print(f末尾添加元素6:{arr})arr.insert(0,0)# 指定位置插入print(f在索引0处插入元素0:{arr})# 删除元素arr.remove(10)# 删除指定值的第一个匹配项print(f删除值为10的元素:{arr})poppedarr.pop()# 弹出最后一个元素print(f弹出最后一个元素{popped}:{arr})popped_at_indexarr.pop(0)# 弹出指定索引的元素print(f弹出索引0的元素{popped_at_index}:{arr})# 切片操作print(f前3个元素 arr[:3]:{arr[:3]})print(f从索引2开始的元素 arr[2:]:{arr[2:]})print(f索引1到3的元素 arr[1:3]:{arr[1:3]})# 查找元素index_of_4arr.index(4)# 查找元素索引print(f元素4的索引:{index_of_4})count_of_2arr.count(2)# 统计元素出现次数print(f元素2出现的次数:{count_of_2})print()# 2. 栈(Stack) - 后进先出(LIFO)print(2. 栈(Stack) - 后进先出(LIFO):)classStack:栈的实现def__init__(self):self.items[]defis_empty(self):判断栈是否为空returnlen(self.items)0defpush(self,item):入栈self.items.append(item)defpop(self):出栈ifself.is_empty():raiseIndexError(栈为空不能执行出栈操作)returnself.items.pop()defpeek(self):查看栈顶元素ifself.is_empty():raiseIndexError(栈为空没有栈顶元素)returnself.items[-1]defsize(self):获取栈的大小returnlen(self.items)def__str__(self):returnf栈内容(底-顶):{self.items}# 使用栈stackStack()print(f创建空栈:{stack})stack.push(1)stack.push(2)stack.push(3)print(f入栈1, 2, 3后:{stack})top_itemstack.peek()print(f栈顶元素:{top_item})popped_itemstack.pop()print(f出栈元素:{popped_item})print(f出栈后:{stack})print(f栈的大小:{stack.size()})# 栈的应用示例括号匹配defis_balanced_parentheses(expression):检查括号是否匹配stackStack()opening([{closing)]}pairs{(:),[:],{:}}forcharinexpression:ifcharinopening:stack.push(char)elifcharinclosing:ifstack.is_empty():returnFalseifpairs[stack.pop()]!char:returnFalsereturnstack.is_empty()# 测试括号匹配expressions[(),()[]{},(],([)],{[]}]forexprinexpressions:resultis_balanced_parentheses(expr)print(f{expr} 括号匹配:{result})print()# 3. 队列(Queue) - 先进先出(FIFO)print(3. 队列(Queue) - 先进先出(FIFO):)fromcollectionsimportdequeclassQueue:队列的实现def__init__(self):self.itemsdeque()defis_empty(self):判断队列是否为空returnlen(self.items)0defenqueue(self,item):入队self.items.append(item)defdequeue(self):出队ifself.is_empty():raiseIndexError(队列为空不能执行出队操作)returnself.items.popleft()deffront(self):查看队首元素ifself.is_empty():raiseIndexError(队列为空没有队首元素)returnself.items[0]defsize(self):获取队列的大小returnlen(self.items)def__str__(self):returnf队列内容(首-尾):{list(self.items)}# 使用队列queueQueue()print(f创建空队列:{queue})queue.enqueue(1)queue.enqueue(2)queue.enqueue(3)print(f入队1, 2, 3后:{queue})front_itemqueue.front()print(f队首元素:{front_item})dequeued_itemqueue.dequeue()print(f出队元素:{dequeued_item})print(f出队后:{queue})print(f队列的大小:{queue.size()})# 队列的应用示例任务调度模拟defsimulate_print_queue(tasks):模拟打印队列print_queueQueue()# 添加任务到队列fortaskintasks:print_queue.enqueue(task)print(f任务 {task} 已添加到打印队列)# 处理任务whilenotprint_queue.is_empty():current_taskprint_queue.dequeue()print(f正在打印:{current_task})# 测试任务调度tasks[文档1.pdf,图片2.png,报告3.docx]print(打印队列模拟:)simulate_print_queue(tasks)print()# 4. 双端队列(Deque)print(4. 双端队列(Deque):)# 使用collections.dequedqdeque([1,2,3])print(f创建双端队列:{list(dq)})# 在两端添加元素dq.appendleft(0)# 左端添加dq.append(4)# 右端添加print(f左端添加0右端添加4:{list(dq)})# 从两端删除元素left_poppeddq.popleft()# 左端删除right_poppeddq.pop()# 右端删除print(f从左端删除{left_popped}从右端删除{right_popped}:{list(dq)})# 旋转操作dq.rotate(1)# 向右旋转1位print(f向右旋转1位:{list(dq)})dq.rotate(-2)# 向左旋转2位print(f向左旋转2位:{list(dq)})print(\n 线性数据结构详解结束 )架构图线性数据结构 ├── 数组(List) │ ├── 创建 │ ├── 访问 │ ├── 修改 │ ├── 添加 │ ├── 删除 │ ├── 切片 │ └── 查找 ├── 栈(Stack) │ ├── 入栈(push) │ ├── 出栈(pop) │ ├── 查看栈顶(peek) │ ├── 判空(is_empty) │ └── 大小(size) ├── 队列(Queue) │ ├── 入队(enqueue) │ ├── 出队(dequeue) │ ├── 查看队首(front) │ ├── 判空(is_empty) │ └── 大小(size) └── 双端队列(Deque) ├── 左右端添加 ├── 左右端删除 └── 旋转操作应用场景流程图栈应用 - 括号匹配: 1. 遍历表达式 ├── 字符类型判断 │ ├── 左括号 → 入栈 │ ├── 右括号 → 栈是否为空? │ │ ├── 是 → 返回false │ │ └── 否 → 出栈并匹配 │ │ ├── 匹配 → 继续遍历 │ │ └── 不匹配 → 返回false │ └── 其他字符 → 继续遍历 └── 遍历完成 → 检查栈是否为空 ├── 栈为空 → 返回true └── 栈非空 → 返回false特点对比数据结构主要操作时间复杂度适用场景数组随机访问: O(1)插入/删除: O(n)需要频繁访问元素栈插入/删除: O(1)访问: O(n)后进先出场景队列入队/出队: O(1)访问: O(n)先进先出场景双端队列两端操作: O(1)中间操作: O(n)需要在两端操作元素