还剩17页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《线性表栈队列》ppt课件THE FIRSTLESSON OFTHE SCHOOLYEARCONTENTS目录•线性表•栈•队列•线性表、栈、队列的比较01线性表线性表的定义010203线性表的定义线性表的特性线性表的分类线性表是一种具有固定数线性表中的元素具有排列根据元素之间的关系,线量元素的数据结构,元素性,即元素在表中的位置性表可以分为顺序存储和之间存在一对一的线性关是确定的,可以通过下标链式存储两种类型系进行访问线性表的基本操作插入操作删除操作查找操作修改操作在指定位置插入一个新删除指定位置的元素,根据元素的值查找其在修改指定位置的元素的元素,保持线性表的顺保持线性表的顺序性表中的位置值序性线性表的实现顺序存储实现链式存储实现线性表的应用使用数组实现线性表,通使用链表实现线性表,通线性表在实际应用中非常过下标访问元素,具有访过指针访问元素,具有动广泛,如数组、链表、队问速度快、空间利用率高态分配空间、便于插入和列、栈等都是基于线性表等优点删除等优点实现的数据结构01栈栈的定义栈的特点栈具有后进先出的特性,即最后进栈的定义入栈的元素将最先被删除,而最早进入栈的元素将最后被删除栈是一种具有后进先出(LIFO)特性的线性表,只允许在表的一端进行插入和删除操作栈的应用栈在计算机科学中有着广泛的应用,如括号匹配、函数调用堆栈、深度优先搜索等栈的基本操作压栈(push)弹栈(pop)将一个元素添加到栈顶删除栈顶元素并返回其值查看栈顶(peek)判断栈是否为空(isEmpty)返回栈顶元素的值,但不删除它检查栈是否为空,如果为空则返回true,否则返回false栈的实现顺序栈使用数组来实现栈,通过维护两个指针,一个指向栈顶元素,另一个指向栈底元素顺序栈具有空间利用率高的优点,但在某些情况下可能会导致空间浪费链式栈使用链表来实现栈,每个节点包含数据域和指针域链式栈可以动态地分配和回收空间,但需要额外的指针操作01队列队列的定义01队列是一种特殊的线性表,只允许在表的前端(front)进行删除操作,在表的后端(rear)进行插入操作02队列具有先进先出(FIFO)的特性,最早进入队列的元素将最先出队队列的基本操作01020304判断队列是否为空检入队操作(Enqueue)出队操作(Dequeue)获取队头元素返回队查队列是否为空,如果在队列的尾部添加一个删除队列头部的元素并列头部的元素,但不删为空则返回true,否则元素返回除返回false队列的实现链表实现01使用链表作为底层数据结构来实现队列,每个节点包含数据和指向下一个节点的指针链表实现允许动态调整队列的大小数组实现02使用数组作为底层数据结构来实现队列,数组的每个元素表示一个节点数组实现具有较好的随机访问性能,但插入和删除操作可能需要移动大量元素双端队列实现03使用双端队列(deque)作为底层数据结构来实现队列,双端队列允许在两端进行插入和删除操作双端队列实现可以同时利用两个端点进行操作,提高效率01线性表、栈、队列的比较操作的比较线性表队列队列是一种先进先出(FIFO)的数据线性表是一种一维的数据结构,常见结构,常见的操作有入队、出队、查的操作有插入、删除、查找等看队首元素等栈栈是一种后进先出(LIFO)的数据结构,常见的操作有压栈、弹栈、查看栈顶元素等应用场景的比较线性表栈队列适用于需要按顺序存储和访问数适用于需要后进先出处理数据的适用于需要先进先出处理数据的据的情况,如学生成绩单的存储情况,如括号匹配、函数调用等情况,如打印机的打印任务队列、和排序操作系统中的任务调度等优缺点的比较线性表优点是操作简单、实现方便;缺点是插入和删除操作需要移动大量元素,效率较低栈优点是后进先出的处理方式简单直观;缺点是只能在一端进行插入和删除操作,限制了其应用场景队列优点是先进先出的处理方式符合大多数实际需求;缺点是只能在一端插入和另一端删除,限制了其应用场景感谢观看THANKSTHE FIRSTLESSON OFTHE SCHOOLYEAR。