数据结构第二章讲稿同学们好！我们今天学习“数据结构”第三章“栈和队列”。3.0总结:我们说数据结构第2、3、4、5都讨论线性结构，第二章线性表讨论最普遍意义上的线性结构，在第二章，我们讨论了线性表的两种实现方式，顺序映射与链式映射，引用型操作较多的情况下，适于采用顺序映射，在顺序映射的情况下，因为元素顺序存储，且属于同一种数据类型，所以读取第i个元素操作的时间复杂度为常量阶的，但插入与删除我们要平均移动一半的数据元素。在链式映射的情况下，因为元素的存储位置任意，读取元素时只能“顺藤摸瓜”的方式进行，时间复杂度为O（n），虽然插入、删除元素不需要移动元素，仅需要修改第i-1个元素（在双向链表时还需要修改第i1个元素的指针）相关指针，但因为找到第i1个元素的所需要的时间为O（n）。我们找更高效插入、删除算法的目的没有达到。请同学们记住这一点。无论顺序表还是链表，我们插入元素时有n1个位置可以选择，删除元素时有n个位置可以选择。但是在有些具体应用中，插入删除仅能在线性表的一端或两端进行。思考：1.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n
