浅谈栈和队列资料.pptx

《浅谈栈和队列资料.pptx》由会员分享，可在线阅读，更多相关《浅谈栈和队列资料.pptx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、会计学1浅谈栈和队列资料浅谈栈和队列资料摘要摘要 栈和队列是常见的数据结构，是两种非常重栈和队列是常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。从数据结构角度看，栈和和循环队列等形式。从数据结构角度看，栈和队列是受限的线性表，栈和队列的数据元素具队列是受限的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系。他们广泛应有单一的前驱和后继的线性关系。他们广泛应用在操作系统和编译程序等各种软件系统中。用在操作系统和编译程序等各种软件系

2、统中。第1页/共19页论文提纲论文提纲 1 1 栈栈栈栈1 2 2 队列队列队列队列2 3 3 栈的队列的应用区别栈的队列的应用区别栈的队列的应用区别栈的队列的应用区别3 4 4 栈和队列的发展前景栈和队列的发展前景栈和队列的发展前景栈和队列的发展前景4结束第2页/共19页 引言引言引言引言 在对高级语言编写的源程序进行编译时类在对高级语言编写的源程序进行编译时类似于表达式括号匹配问题就是用栈来解决似于表达式括号匹配问题就是用栈来解决的；计算机系统在处理子程序之间的调用的；计算机系统在处理子程序之间的调用关系是，用栈来保存处理执行过程中的调关系是，用栈来保存处理执行过程中的调用次序。现实世界中

3、有许多问题可以用队用次序。现实世界中有许多问题可以用队列描述。例如，对顾客服务部门的工作往列描述。例如，对顾客服务部门的工作往往是按照队列方式进行的，这类系统乘坐往是按照队列方式进行的，这类系统乘坐排队系统。程序设计中，也经常使用队列排队系统。程序设计中，也经常使用队列记录需按照先进先出方式处理的数据，例记录需按照先进先出方式处理的数据，例如键盘缓冲区，操作系统中的作业调度等。如键盘缓冲区，操作系统中的作业调度等。返回到总目录第3页/共19页1 栈栈1.1 1.1 栈的概念栈的概念 栈（栈（stackstack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净）是一种特殊的线性表。作为

4、一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。如果我们把冼净的碗先取用，后摞上的先取用。如果我们把冼净的碗“摞上摞上”称为进栈（压栈），称为进栈（压栈），把把“取用碗取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个线性表，只不过而，

5、摞起来的碗实际上是一个线性表，只不过“进栈进栈”和和“出栈出栈”都在最顶都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。第4页/共19页 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。插入元素又称为进栈，删除元素又称为出栈。允许进行插入和删除操作的一端称为栈顶（top），另一端称为栈（bottom）。处于栈顶位置的数据元素称为栈顶元素，处于栈底位置的数据元素称为栈底元素。不含任何数据元素的栈称为空栈。第5页/共19页1.2栈的基本操作栈的基本操作 栈除了在栈顶进行进栈

6、与出栈外，还有初始化、判空等操作，常用的基本操栈除了在栈顶进行进栈与出栈外，还有初始化、判空等操作，常用的基本操作有：作有：（1 1）初始化栈）初始化栈InitStack(S)InitStack(S)。其作用是构造一个空栈。其作用是构造一个空栈S S。（2 2）判断栈空）判断栈空EmptyStack(S)EmptyStack(S)。其作用是判断是否是空栈，若栈。其作用是判断是否是空栈，若栈S S为空，则返回为空，则返回1 1；否则返回否则返回0 0。（3 3）进栈）进栈Push(S,x)Push(S,x)。其作用是当栈不为满时，将数据元素。其作用是当栈不为满时，将数据元素x x插入栈插入栈S

7、S中，使其为栈中，使其为栈S S的栈顶元素。的栈顶元素。（4 4）出栈）出栈Pop(S,x)Pop(S,x)。其作用是当栈。其作用是当栈S S不为空时，将栈顶元素赋给不为空时，将栈顶元素赋给x x，并从栈，并从栈S S中删除中删除当前栈顶元素。当前栈顶元素。（5 5）取栈顶元素）取栈顶元素GetTop(S,x)GetTop(S,x)。其作用是当栈。其作用是当栈S S不为空时，将栈顶元素赋给不为空时，将栈顶元素赋给x x并返回，并返回，操作结果只是读取栈顶元素，栈操作结果只是读取栈顶元素，栈S S不发生变化。不发生变化。第6页/共19页 由由于于栈栈是是操操作作受受限限制制的的线线性性表表，因因

8、此此与与线线性性表表类类似似，栈栈也也有有两两种种存储结构，即顺序存储结构和链式存储结构。存储结构，即顺序存储结构和链式存储结构。1.3.11.3.1顺序栈顺序栈 栈栈的的顺顺序序存存储储结结构构称称为为顺顺序序栈栈。类类似似于于顺顺序序表表的的类类型型定定义义，顺顺序序栈栈是是用用一一个个预预设设的的足足够够长长度度的的一一维维数数组组和和一一个个记记录录栈栈顶顶元元素素位位置置的的变变量量来实现。来实现。1.3.21.3.2链栈链栈 用用链链式式存存储储结结构构实实现现的的栈栈称称为为链链栈栈33，链链栈栈与与不不带带头头结结点点单单链链表表组组织织形形式式相相似似，因因为为栈栈的的主主要

9、要操操作作是是在在栈栈顶顶进进行行插插入入与与删删除除操操作作，显显然然将将链链表表的的第第一一个个结结点点作作为为栈栈顶顶是是最最方方便便的的，因因此此，没没有有必必要要如如单单链链表那样为了操作方便附加一个头结点。表那样为了操作方便附加一个头结点。链栈的基本操作实现也有初始化栈操作，判断栈空操作，进栈操作，链栈的基本操作实现也有初始化栈操作，判断栈空操作，进栈操作，出栈操作，取栈顶元素。出栈操作，取栈顶元素。1.3栈的分类栈的分类第7页/共19页 2.1 2.1 队列的概念队列的概念 在在日日常常生生活活中中的的排排队队上上车车，排排队队的的规规则则是是不不允允许许“插插队队”。后后来来的

10、的人人需需站站在在队队尾尾，每每次次总总是是队队头头先先上上车车。这这种种先先进进先先出出的的规规则则应应用用在在数数据据结结构构中中称称为为队队列列（queuequeue），队队列列又又称称为为先先进进先先出出（first first in in first first outout）的的线线性性表表，简称简称FIFOFIFO表。表。队队列列也也是是一一种种特特殊殊的的线线性性表表44。与与栈栈不不同同，其其插插入入操操作作限限定定在在线线性性表表的的一一端端进进行行，删删除除操操作作限限定定在在线线性性表表的的另另一一端端进进行行，队队列列插插入入操操作作又又称称为为入入队队，删删除除操操

11、作作又又称称为为出出队队，允允许许进进行行插插入入的的一一端端称称为为队队尾尾（rearrear），允允许许进进行行删删除除的的一一端端称称为为队队头头（frontfront）。处处于于队队头头位位置置的的数数据据元元素素称称为为队队头头元元素素。处处于于队队尾尾位位置置的的数数据据元元素素称称为为队队尾尾元素。不含任何数据元素的队列称为空队元素。不含任何数据元素的队列称为空队。2队列队列第8页/共19页2.2 2.2 队列的基本操作队列的基本操作 队列的除了在队头进行出队和队尾进行入队外，还有初始化、判队列的除了在队头进行出队和队尾进行入队外，还有初始化、判空等操作，常用的基本操作有：空等操

12、作，常用的基本操作有：（1 1）初始化队列）初始化队列InitQueue(Q)InitQueue(Q)。其作用是构造一个空队列。其作用是构造一个空队列QQ。（2 2）判断队列空）判断队列空EmptyQueue(Q)EmptyQueue(Q)。其作用是判断是否是空队列，若队。其作用是判断是否是空队列，若队列列QQ为空，则返回为空，则返回1 1；否则返回；否则返回0 0。（3 3）入队）入队EnQueue(Q,x)EnQueue(Q,x)。其作用是当队列不为满时，将数据元素。其作用是当队列不为满时，将数据元素x x插插入队列入队列QQ的队尾，使其为队列的队尾，使其为队列QQ的队尾元素。的队尾元素。

13、（4 4）出队）出队DeQueue(Q,x)DeQueue(Q,x)。其作用是当队列。其作用是当队列QQ不为空时，将队头元素赋不为空时，将队头元素赋给给x x，并从队列，并从队列QQ中删除当前队头元素，而其后继元素成为队头元中删除当前队头元素，而其后继元素成为队头元素。素。（5 5）取队头元素）取队头元素GetFront(Q,x)GetFront(Q,x)。其作用是当队列。其作用是当队列QQ不为空时，将队头不为空时，将队头元素赋给元素赋给x x并返回，操作结果只是读取队头元素，队列并返回，操作结果只是读取队头元素，队列QQ不发生变不发生变化。化。UGS第9页/共19页 由于队列是操作受限制的线

14、性表，因此与线性表类似，由于队列是操作受限制的线性表，因此与线性表类似，队列也有两种存储结构，即顺序存储结构和链式存储队列也有两种存储结构，即顺序存储结构和链式存储结构。结构。队列的顺序存储结构需要使用一个数组和两个整型变队列的顺序存储结构需要使用一个数组和两个整型变量来实现，利用数组来顺序存储队列中的所有元素，量来实现，利用数组来顺序存储队列中的所有元素，利用两个整型变量来分别存储队首元素和队尾元素的利用两个整型变量来分别存储队首元素和队尾元素的下标位置，分别称它们为队首指针和队尾指针。下标位置，分别称它们为队首指针和队尾指针。队列也是操作受限的线性表。限定在队尾处插队列也是操作受限的线性表

15、。限定在队尾处插入，而在队头处删除。入，而在队头处删除。队列是先进先出（队列是先进先出（First In First OoutFirst In First Oout，FIFOFIFO）的线性）的线性表。表。UGS第10页/共19页 约定队列的头指针约定队列的头指针frontfront指向队列头元素前一位置，而为指针指向队列头元素前一位置，而为指针rearrear指向队尾元素自身。循环队列是重要数据结构，即指队列的顺序指向队尾元素自身。循环队列是重要数据结构，即指队列的顺序存储结构。凡涉及队头或队尾指针的修改都要对存储结构。凡涉及队头或队尾指针的修改都要对MAXSIZEMAXSIZE求模：求模：

16、front=(front+1)%MAXSIZE;front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;循环队列，队空的判定条件：循环队列，队空的判定条件：rear=frontrear=front；循环队列，队满的的判定条件是：循环队列，队满的的判定条件是：(rear+1)%MAXSIZE=front(rear+1)%MAXSIZE=front；队列的链式存储结构称为链队列。通常设附加头结点，并设队头队列的链式存储结构称为链队列。通常设附加头结点，并设队头指针指向头结点，即指向第一个数据结点的前一位置。队列的尾指针

17、指向头结点，即指向第一个数据结点的前一位置。队列的尾指针指向终端结点。指针指向终端结点。链队列的基本操作，也是单链表操作的简化，插入只考虑在链队列链队列的基本操作，也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为为O(1)O(1)。UGS第11页/共19页1.1.队列先进先出，栈先进后出。队列先进先出，栈先进后出。2.2.对插入和删除操作的对插入和删除操作的 限定限定。栈是限定只能在表的栈是限定只能在表的一端进行插入和删除操作的线性表。一端进行插入和删除操作的线性表。队列是限定只能队列是限

18、定只能在表的一端进行插入和在另一端进行删除操作的线性在表的一端进行插入和在另一端进行删除操作的线性表。从表。从 数据结构数据结构 的角度看，它们都是线性结构，即的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的是对插入和删除操作的 限定限定。栈和队列是在程序设。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按于基本操作的特殊

19、性，栈必须按 后进先出后进先出 的规则进的规则进行操作，而队列必须按行操作，而队列必须按 先进先出先进先出 的规则进行操作。的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。和限定，故又称为限定性的线性表结构。3栈和队列的应用区别栈和队列的应用区别UGS第12页/共19页 3.3.遍遍历历数数据据速速度度不不同同。栈栈只只能能从从头头部部取取数数据据 也也就就最最先先放放入入的的需需要要遍遍历历整整个个栈栈最最后后才才能能取取出出来来，而而且且在在遍遍历历数数据据的的时时候候还还得得为为数数据据开开辟

20、辟临临时时空空间间，保保持持数数据据在在遍遍历历前前的的一一致致性性队队列列怎怎不不同同，他他基基于于地地址址指指针针进进行行遍遍历历，而而且且可可以以从从头头或或尾尾部部开开始始遍遍历历，但但不不能能同同时时遍遍历历，无无需需开开辟辟临临时时空空间间，因因为为在在遍遍历历的的过过程程中中不不影影像像数数据据结结构构，速速度度要要快快的的多多。栈栈（StackStack）是是限限定定只只能能在在表表的的一一端端进进行行插插入入和和删删除除操操作作的的线线性性表表。队队列列（QueueQueue）是是限限定定只只能能在在表表的的一一端端进进行行插插入入和和在在另另一一端端进进行行删删除除操操作作

21、的的线线性性表表。从从 数数据据结结构构 的的角角度度看看，它它们们都都是是线线性性结结构构，即即数数据据元元素素之之间间的的关关系系相相同同。但但它它们们是是完完全全不不同同的的数数据据类类型型。除除了了它它们们各各自自的的基基本本操操作作集集不不同同外外，主主要要区区别别是是对对插插入入和和删删除除操操作作的的 限限定定。栈栈和和队队列列是是在在程程序序设设计计中中被被广广泛泛使使用用的的两两种种线线性性数数据据结结构构，它它们们的的特特点点在在于于基基本本操操作作的的特特殊殊性性，栈栈必必须须按按 后后进进先先出出 的的规规则则进进行行操操作作，而而队队列列必必须须按按 先先进进先先出出

22、 的的规规则则进进行行操操作作。和和线线性性表表相相比比，它它们们的的插插入入和和删删除除操操作受更多的约束和限定，故又称为限定性的线性表结构作受更多的约束和限定，故又称为限定性的线性表结构。UGS第13页/共19页 栈和队列在各类系统中应用广泛。堆栈技术被广泛应用于编译软件和程序设计，操作系统、事务管理中广泛应用了队列技术。讨论堆栈与队列的结构特征与实现特点，有重要意义。4 4栈和队列的发展前景栈和队列的发展前景UGS第14页/共19页 目前，国内外关于数据结构中栈和队列这两种限定性线性表的研究都只局限于传统的单栈、单循环队列、双端栈、链栈等存储结构，在实际的课堂教学中也只涉及到这些内容，这

23、些存储结构大多事先开辟好定量存储空间，导致了在具体应用中存储空间不同程度的浪费，以往文献未就此问题做深入探究以求解决。所以，关于栈和队列我们还有许多要改善的和提高的，只有这样，才能让操作程序更高效化，便捷化。UGS第15页/共19页 谢谢！再见！UGS第16页/共19页人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。第17页/共19页第18页/共19页