浅谈栈和队列资料课件.pptVIP

浅谈栈和队列

摘要

论文提纲11栈2342队列3栈的队列的应用区别4栈和队列的发展前景结束

引言在对高级语言编写的源程序进行编译时类似于表达式括号匹配问题就是用栈来解决的；计算机系统在处理子程序之间的调用关系是，用栈来保存处理执行过程中的调用次序。现实世界中有许多问题可以用队列描述。例如，对顾客服务部门的工作往往是按照队列方式进行的，这类系统乘坐排队系统。程序设计中，也经常使用队列记录需按照先进先出方式处理的数据，例如键盘缓冲区，操作系统中的作业调度等。返回到总目录

1栈1.1栈的概念栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。插入元素又称为进栈，删除元素又称为出栈。允许进行插入和删除操作的一端称为栈顶（top），另一端称为栈（bottom）。处于栈顶位置的数据元素称为栈顶元素，处于栈底位置的数据元素称为栈底元素。不含任何数据元素的栈称为空栈。

1.2栈的基本操作栈除了在栈顶进行进栈与出栈外，还有初始化、判空等操作，常用的基本操作有：（1）初始化栈InitStack(S)。其作用是构造一个空栈S。（2）判断栈空EmptyStack(S)。其作用是判断是否是空栈，若栈S为空，则返回1；否则返回0。（3）进栈Push(S,x)。其作用是当栈不为满时，将数据元素x插入栈S中，使其为栈S的栈顶元素。（4）出栈Pop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x，并从栈S中删除当前栈顶元素。（5）取栈顶元素GetTop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x并返回，操作结果只是读取栈顶元素，栈S不发生变化。

1.3栈的分类。

2队列。

2.2队列的基本操作队列的除了在队头进行出队和队尾进行入队外，还有初始化、判空等操作，常用的基本操作有：（1）初始化队列InitQueue(Q)。其作用是构造一个空队列Q。（2）判断队列空EmptyQueue(Q)。其作用是判断是否是空队列，若队列Q为空，则返回1；否则返回0。（3）入队EnQueue(Q,x)。其作用是当队列不为满时，将数据元素x插入队列Q的队尾，使其为队列Q的队尾元素。（4）出队DeQueue(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x，并从队列Q中删除当前队头元素，而其后继元素成为队头元素。（5）取队头元素GetFront(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x并返回，操作结果只是读取队头元素，队列Q不发生变化。UGS

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

约定队列的头指针front指向队列头元素前一位置，而为指针rear指向队尾元素自身。循环队列是重要数据结构，即指队列的顺序存储结构。凡涉及队头或队尾指针的修改都要对MAXSIZE求模：front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;循环队列，队空的判定条件：rear==front；循环队列，队满的的判定条件是：(rear+1)%MAXSIZE==front；队列的链式存储结构称为链队列。通常设附加头结点，并设队头指针指向头结点，即指向第一个数据结点的前一位置。队列的尾指针指向终端结点。链队列的基本操作，也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为O(1)。UGS

3栈和队列的应用区别UGS

。UGS

4栈和队列的发展前景UGS

目前，国内外关于数据结构中栈和队列这两种限定性线性表的研究都只局限于传统的单栈、单循环队列、双端栈、链栈等存储结构，在实际的课堂教学中也只涉及到这些内容，这些存储结构大多事先开辟好定量存储空间，导致了在具体应用中存储空间不同程度的浪费，以往文献未就此问题做深入探究以求