Python数据结构与算法-第3章-线性数据结构

一案例：简单的计算器案例：简单的计算器案例描述

实现一个简单的计算器。这个计算器可以进行基本的加减乘除运，允许用户在控制台输入两个数和运算符，程序会根据用户的输入自动计算并输出结果。简单起见，我们只考虑两个整数之间的运算。案例：简单的计算器案例实现实现形式1实现形式2优化后↓借用线性数据结构栈的特性实现的计算器，主要使用了栈来处理运算符和操作数（具体见课本案例）（具体见课本案例）案例：简单的计算器案例实现上图为“遍历计算表达式对应栈操作过程”案例：简单的计算器案例实现上图为“运算符栈和操作数栈剩余元素对应栈操作过程”案例：简单的计算器案例实现实现形式1实现形式2优化后↓实现方式采用分开获取用户输入的操作数和操作符并采用分支结构进行判定的计算器，只能实现单个的运算符的简单运算。使用线性数据结构中的栈实现计算器，利用的栈的“后进先出”特性可以处理更为复杂的表达式。并且可以自动处理运算符的优先级，不需要手动添加括号。（具体见课本案例）（具体见课本案例）二线性数据结构的概念线性数据结构的概念数据结构的分类数组链表栈栈队列树图……堆线性数据结构非线性数据结构线性数据结构的概念线性数据结构上图为“线性数据结构示例”

线性数据结构是一种数据元素排成线性序列的数据结构。线性数据结构的元素按照一定的线性顺序排列，它们之间存在一种单一的、线性的关系。线性数据结构的概念非线性数据结构上图为“非线性数据结构示例”

非线性数据结构是指其中元素之间不是简单、顺序地排列的数据结构。非线性数据结构中的元素之间存在着复杂的关系，这种关系可以是层次关系、分支关系或任意复杂的关系。三数

组数组数组的概念上图为“数组的逻辑结构和物理结构”一致性不可变性有序性特点数组数组的操作0102030405访问元素创建数组删除元素插入元素遍历元素06查找元素数组数组的优缺点优点缺点访问元素快速插入和删除元素效率慢更适合的访问频繁，但插入和删除操作较少的场景数组数组的应用1字符串处理2图形和图像处理3数学计算4算法和数据结构5网络编程6缓存管理四链

表链表链表的概念上图为“链表的逻辑结构和物理结构”头节点尾节点特殊的节点链表链表的实现及操作0102030405遍历链表创建链表删除节点插入节点访问节点06查找节点链表链表的优缺点优点缺点动态大小插入和删除操作效率高内存空间要求低查找效率低额外的空间开销缺乏直接访问链表链表的扩展环形链表示例双向链表示例链表链表的应用1实现其他数据结构2内存分配3文件系统4浏览器历史记录5数据缓冲区五栈栈栈的概念上图为“栈的基本概念”栈栈的数组实现及操作0102030405入栈操作出栈操作查看栈大小栈判空查处栈顶元素栈栈的链表实现及操作0102030405入栈操作出栈操作查看栈大小栈判空查处栈顶元素栈栈的实现及操作栈逻辑操作和底层链表变化栈逻辑操作和底层数组变化栈栈的优缺点优点缺点插入和删除操作效率高访问栈顶元素快速插入、删除元素可能会造成内存空间浪费不能直接访问栈中间或底部的元素以数组实现以链表实现占用的内存空间就相对较大栈栈的应用1函数调用和递归2内存管理3浏览器前进和后退4编辑器的撤销功能5迷宫求解六队

列栈队列的概念左图为“队列的概念”栈基于Python内置队列的实现及操作1.queue模块的Queue类（具体见课本案例）2.collections模块的deque类（具体见课本案例）适用于多线程环境，需要阻塞等待或其他高级队列功能的场景可以在队列的两端执行快速的添加和弹出操作，同时也可以通过使用额外的同步机制（例如锁）来确保线程安全。栈基于链表实现队列的实现及操作上图为“基于链表实现队列对应操作”栈基于数组队列的实现及操作上图为“基于数组实现队列对应操作”栈基于环形数组队列的实现及操作上图为“基于环形数组实现队列对应操作”下图为“环形数组概念”栈队列的优缺点优点缺点确保了元素的顺序性时间复杂度降低到O(1)需要的存储空间相对较大固定的容量限制栈队列的应用1系统订单高并发处理2网络数据包传输3排队取号4广度优先搜索5消息队列七小结与习题小结与习题本章小结1数组234链表栈队列小结与习题习题？？以下关于数组的描述正确的是?A.不需要事先指定大小

B.存储元素的内存空间是连续的C.可以存储不同类型的数据

D.不支持随机访问在链表中进行随机访问的时间复杂度是?A.O(1)

B.O(logn)C.O(n)

D.O(n2)小结与习题习题？？以下哪个数据结构是具备先进先出（FIFO）特性的?A.栈

B.队列C.链表

D.数组以下哪个队列的操作的时间复杂度不是O(1)?A.入队

B.出队C.查看队首元素

D.随机访问元素小结与习题习题×/√数组的插入操作比链表更有效率。×/√链表中的节点可以在内存中分布不连续。×/√链表是一种线性数据结构，其特点是先进后出（LastInFirstOut，LIFO）栈可以使用列表来实现。×/√小结与习题习题

？对于一个包含5个元素的整数数组，要访问第三个元素，需要使用的索引值为____。

？在使用链表实现队列时，需要维护队首节点和队尾节点，分别记录队首元素和队尾元素的____。

？在使用链表实现队列时，入队操作需要更新____的指针/引用。八实训任务实训任务任务设计一个餐厅点单系统的简化版本。该系统需要模拟餐厅接收订单、处理订单的流程。实现一个队列系统，确保订单按照先进先出的原则被处理。每个订单包含订单号