栈与队列(一)

1、第十一章第十一章堆栈与队列（一）堆栈与队列（一）引入栈和队列1234栈和队列是栈和队列是操作受限操作受限的线性表的线性表 栈和队列是操作受限操作受限的线性表； 通常称，栈和队列是限定插入插入和和删除删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型主要内容主要内容 堆栈的概念及其运算堆栈的概念及其运算 栈的抽象类定义栈

2、的抽象类定义 栈的定义及其实现栈的定义及其实现 堆栈的应用举例堆栈的应用举例11.1 堆栈的概念及其运算堆栈的概念及其运算 n堆栈的定义堆栈的定义n堆栈的特点堆栈的特点n堆栈的示意图堆栈的示意图n堆栈的有关运算堆栈的有关运算 堆栈的定义堆栈的定义n堆栈是一种只允许在堆栈是一种只允许在表的一端进表的一端进行插入和删除运算行插入和删除运算的线性表；的线性表；n允许进行运算的一端称为允许进行运算的一端称为栈顶栈顶，另一端则称为另一端则称为栈底栈底；n当表中没有元素时，称为当表中没有元素时，称为空栈空栈；n堆栈的插入运算简称为堆栈的插入运算简称为入栈或进入栈或进栈栈，删除运算简称为，删除运算简称为出栈

3、或退栈出栈或退栈。出栈出栈进栈进栈栈的示意图栈的示意图栈顶栈顶栈底栈底a an na a2 2a a1 1 堆栈的特点堆栈的特点出栈出栈进栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底第一个进栈的元素在栈底最后一个进栈的元素在栈顶最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元最后一个出栈的元素为栈底元素素栈的示意图栈的示意图栈顶栈顶栈底栈底a an na a2 2a a1 1堆栈的有关运算堆栈的有关运算n进栈运算进栈运算：在堆栈的顶端插入一个新元素，相当：在堆栈的顶端插入一个新元素，相当于在线性表最后的元素之后再插入一个新元

4、素；于在线性表最后的元素之后再插入一个新元素；n出栈运算出栈运算：删除栈顶的元素，在实际应用中，经：删除栈顶的元素，在实际应用中，经常要用到栈顶元素。所以，栈顶元素一般应先保常要用到栈顶元素。所以，栈顶元素一般应先保存，再删除栈顶结点；存，再删除栈顶结点；n清栈运算清栈运算：用来将栈清空；：用来将栈清空；n测试栈空测试栈空：测试当前栈是否为空，栈空时，不能：测试当前栈是否为空，栈空时，不能进行出栈运算。下溢；进行出栈运算。下溢；n测试栈满测试栈满：测试当前栈是否为满，栈满时，不能：测试当前栈是否为满，栈满时，不能进行入栈运算。上溢。进行入栈运算。上溢。11.2 栈的抽象类定义栈的抽象类定义te

5、mplate /定义一个抽象的模板堆栈类定义一个抽象的模板堆栈类class abstack public: bool IsEmpty( ) /判断堆栈是否为空判断堆栈是否为空 return (height=0)?true:false; /进栈函数，将一元素压入栈中进栈函数，将一元素压入栈中 virtual void Push(type&)=0; /出栈函数，从栈中取一元素出栈函数，从栈中取一元素 virtual bool Pop(type&)=0; /清栈函数，用于释放栈所占的内存空间清栈函数，用于释放栈所占的内存空间 virtual void Clear( )=0; protected :

6、unsigned height; ; /栈高栈高 （1） 抽象栈类中定义了栈高抽象栈类中定义了栈高height，可简化操作，例如判，可简化操作，例如判断栈空、栈满。断栈空、栈满。height在在abstack类中为类中为protected，它的，它的派生类可以访问它。在抽象栈的数据成员中没有栈顶指派生类可以访问它。在抽象栈的数据成员中没有栈顶指针，因为顺序栈和链栈的栈顶指针具有不同的数据类型，针，因为顺序栈和链栈的栈顶指针具有不同的数据类型，顺序栈顺序栈(整型整型)、链栈、链栈(指针型指针型)；（2） 根据栈的常用操作，在根据栈的常用操作，在abstack类中定义了类中定义了4个函数，个函数，

7、其中其中3个是纯虚函数，其实现与栈的存储结构有关，因个是纯虚函数，其实现与栈的存储结构有关，因此在派生类中给出其定义。此在派生类中给出其定义。nIsEmpty( ); 判定堆栈是否为空或栈高是否为判定堆栈是否为空或栈高是否为0；nPush(type &); 将将type类型的数据元素插入到栈顶；类型的数据元素插入到栈顶；nPop(type &); 将栈顶元素弹出并赋给将栈顶元素弹出并赋给type类型的元素；类型的元素；nClear( ); 将堆栈清空。将堆栈清空。 抽象栈类说明：抽象栈类说明：11.3 栈的定义及其实现栈的定义及其实现n顺序栈的定义顺序栈的定义n顺序栈类的定义及典型成员函顺序栈

8、类的定义及典型成员函数的实现数的实现n多栈共享空间问题多栈共享空间问题 顺序栈的定义顺序栈的定义n设一维数组为设一维数组为STACKmaxsize ;n再设一个再设一个整型变量整型变量top表示表示栈顶指针栈顶指针：当堆栈不空时，当堆栈不空时，top的值就是栈顶元的值就是栈顶元素的素的下标值下标值；当堆栈为；当堆栈为空空时，有时，有top= -1；ntop最大最大取值为取值为maxsize-1。nSTACK0为第一个进入堆栈的元素，为第一个进入堆栈的元素，当当没有删除没有删除运算时，运算时，STACKi-1为为第第i个个进入堆栈的元素，进入堆栈的元素，STACKtop为为栈顶元素栈顶元素top

9、topA AB BM-1210SATCK 顺序栈的示意图顺序栈的示意图toptoptoptopA AB BC CD DE E空栈空栈toptopA AA A进栈进栈B C D EB C D E进栈进栈toptopA AB BE D CE D C出栈出栈称为：栈满称为：栈满顺序栈的定义顺序栈的定义n堆栈是动态结构，存在堆栈是动态结构，存在溢出问题溢出问题。当堆栈。当堆栈中已经有中已经有M个元素时，如果再做进栈运算就个元素时，如果再做进栈运算就会产生溢出，称之为会产生溢出，称之为上溢上溢；对空栈进行删；对空栈进行删除运算也会产生溢出，称之为除运算也会产生溢出，称之为下溢下溢。n为了避免溢出，在对堆

10、栈进行进栈运算和为了避免溢出，在对堆栈进行进栈运算和退栈运算之前都应该分别测试堆栈退栈运算之前都应该分别测试堆栈“是否是否已满已满”或者或者“是否已空是否已空”。 顺序栈类的定义顺序栈类的定义template /定义一个顺序栈类模板定义一个顺序栈类模板class SeqStack: pubilc abstackpublic: SeqStack(int i); /构造函数，构造函数，i用来设置栈的最大高度用来设置栈的最大高度 SeqStack(SeqStack & s) /拷贝构造函数，用于同拷贝构造函数，用于同 copy(s); 类型栈的赋值类型栈的赋值 SeqStack( ) /析构函数，调

11、用析构函数，调用Clear( )函数释放栈所函数释放栈所 Clear( ); 占的内存空间占的内存空间 void Push(type & x); /进栈进栈: 将元素将元素x压入栈中压入栈中 bool Pop(type & x); /出栈出栈: 将栈顶元素值放入将栈顶元素值放入x中中 /清栈函数，用于释放栈所占的内存空间清栈函数，用于释放栈所占的内存空间 void Clear( ) delete elements; SeqStack & Copy(SeqStack & s); /拷贝函数拷贝函数:同类型栈赋值同类型栈赋值 /重载赋值运算符重载赋值运算符“”，用于同类型栈赋值，用于同类型栈赋值

12、SeqStack & operator=(SeqStack & s) delete elements; Copy(s); return *this; bool IsFull( ); /判断栈是否为满判断栈是否为满 return (top= =maxsize-1)?true:false; / top= =maxsize-1为关系表达式为关系表达式protected: int top; /栈顶指针栈顶指针 type *elements; /一维数组指针，用于存放栈中元素一维数组指针，用于存放栈中元素 int maxsize; /栈的最大高度栈的最大高度;(1) 增加了三个数据成员，增加了三个数据成

13、员， top栈顶指针，是整数栈顶指针，是整数下标；下标；elements是指针变量，存放栈元素，在构是指针变量，存放栈元素，在构造函数中对其进行初始化；造函数中对其进行初始化；maxsize表示栈的最表示栈的最大高度，顺序栈的栈高不能超过大高度，顺序栈的栈高不能超过maxsize，否则，否则会溢出；会溢出；(2) 定义了两个构造函数，一个带缺省参数，初始定义了两个构造函数，一个带缺省参数，初始化顺序栈类中数据成员的值，化顺序栈类中数据成员的值，height0，top-1，建空栈。另一个是拷贝构造函数，将另一，建空栈。另一个是拷贝构造函数，将另一个同类型的顺序栈原版拷贝到当前栈。析构函个同类型的

14、顺序栈原版拷贝到当前栈。析构函数数 SeqStack( )调用调用Clear( )函数将堆栈清空。函数将堆栈清空。 顺序栈类定义说明：顺序栈类定义说明： 顺序栈类典型成员函数的实现顺序栈类典型成员函数的实现n构造函数构造函数n进栈函数进栈函数n出栈函数出栈函数n拷贝函数拷贝函数 构造函数构造函数n用于建立栈的对象，为栈的数据用于建立栈的对象，为栈的数据成员赋初值。成员赋初值。首先将栈高置为首先将栈高置为0，将栈顶指针，将栈顶指针top置置为为-1，设置一个空栈；，设置一个空栈；然后，根据参数值，设置最大栈高，然后，根据参数值，设置最大栈高，并为此栈分配内存空间。并为此栈分配内存空间。templ

15、ateSeqStack:SeqStack(int i) height = 0; top = -1; maxsize = i10 ? i:10; /最大栈高最小为最大栈高最小为10 elements = new typemaxsize; assert (elements!=0); /assert为断言语句，参数为断言语句，参数表中给定的条件满足，执行后续语句，否则出错终表中给定的条件满足，执行后续语句，否则出错终止执行止执行 进栈函数进栈函数n首先测试堆栈是否已满。首先测试堆栈是否已满。若栈顶指针若栈顶指针top = maxsize-1，所有位置均已占，所有位置均已占满，若再插入新元素，将产生溢

16、出；满，若再插入新元素，将产生溢出；若栈顶指针若栈顶指针topmaxsize-1，可以插入新元素；，可以插入新元素；先将栈顶指针先将栈顶指针top加加1，指到当前可加入新元素，指到当前可加入新元素的位置，然后将新的元素插在此位置上，这个的位置，然后将新的元素插在此位置上，这个新插入的元素将成为新的栈顶元素。新插入的元素将成为新的栈顶元素。进栈函数进栈函数template /函数模板函数模板void SeqStack:Push(type & x )assert(!IsFull( ); /栈满警告，出错处理栈满警告，出错处理elements+top = x; /将栈顶指针加将栈顶指针加1，将元素，

17、将元素 放入栈顶放入栈顶height+; /栈高加栈高加1 出栈函数出栈函数n首先测试堆栈是否为空栈，若为空栈，首先测试堆栈是否为空栈，若为空栈，出错处理；否则返回栈顶元素的值，并出错处理；否则返回栈顶元素的值，并将其保存在将其保存在x中；中；n将栈顶指针减将栈顶指针减1。出栈函数出栈函数templatebool SeqStack:Pop(type & x) if(IsEmpty( ) /栈空警告，出错处理栈空警告，出错处理 return false; else x = elementstop; /取出栈顶元素，取出栈顶元素， 将其值放入将其值放入x 中中 top- -; /栈顶指针减栈顶指针

18、减1 height- -; /栈高减栈高减1 return true; 拷贝函数拷贝函数templateSeqStack& SeqStack:Copy(SeqStack& s) maxsize = s.maxsize; /设置最大栈高设置最大栈高 elements = new typemaxsize; /为本栈分配内存空间为本栈分配内存空间 assert(elements); /分配失败，提出警告并进分配失败，提出警告并进 行出错处理行出错处理 int len=s.height;for(int i=0; ilen; i+) /从栈底至栈顶，依次将栈从栈底至栈顶，依次将栈 s中的元素赋给本栈中的

19、元素赋给本栈elementsi = *(s.elements+i);top = s.top; /设置新栈栈顶设置新栈栈顶height = s.height; /设置新栈栈高设置新栈栈高return *this;顺序栈的缺点顺序栈的缺点n顺序栈保留着顺序存储的固有缺点，即顺序栈保留着顺序存储的固有缺点，即在重新调整存储空间时，元素的移动量在重新调整存储空间时，元素的移动量较大，尤其在指定的存储空间即将充满较大，尤其在指定的存储空间即将充满时，这种情况更为突出；另外，当栈满时，这种情况更为突出；另外，当栈满时，就会报警。时，就会报警。 多栈共享空间问题多栈共享空间问题n有时在一个程序中，可能需要同

20、时使用两个有时在一个程序中，可能需要同时使用两个或多个堆栈。为了避免溢出，需要为每个堆或多个堆栈。为了避免溢出，需要为每个堆栈分配一个足够大的空间。但带来两个问题：栈分配一个足够大的空间。但带来两个问题： 1. 各个堆栈所需的空间大小很难估计；各个堆栈所需的空间大小很难估计； 2. 由于堆栈是动态结构，各个堆栈的实际大小由于堆栈是动态结构，各个堆栈的实际大小在使用过程中都会发生动态变化，有时其中在使用过程中都会发生动态变化，有时其中一个堆栈产生了上溢，而其它堆栈还留有很一个堆栈产生了上溢，而其它堆栈还留有很多可用空间。多可用空间。 多栈共享空间问题多栈共享空间问题n考虑多栈共享一个大的内存空间

21、，要解决相考虑多栈共享一个大的内存空间，要解决相应产生的问题。应产生的问题。n设将多个堆栈顺序地映射到一个已知大小为设将多个堆栈顺序地映射到一个已知大小为m的存储空间的存储空间STACKm上。上。 多栈共享空间问题多栈共享空间问题1、 两个堆栈共享两个堆栈共享该存储空间：第一个栈底位于该存储空间：第一个栈底位于STACK0，另一个栈底位于，另一个栈底位于STACK m-1。使用时两栈各自向中间伸展，仅当两个栈顶使用时两栈各自向中间伸展，仅当两个栈顶指针相遇（指针相遇（S1. top = S2. top）时才发生上溢。）时才发生上溢。aS10bS11cS124S233S222S211S20STA

22、CK0STACKm-1S1.topS2.top 2、两个以上堆栈共享两个以上堆栈共享该存储空间该存储空间(大小为大小为m)：n将将m个存储空间平均分配给个存储空间平均分配给n个栈，每个栈个栈，每个栈的存储空间为的存储空间为m/n。n设设topn为为n个堆栈的栈顶指针集合，个堆栈的栈顶指针集合，topi为第为第i个堆栈的栈顶指针，个堆栈的栈顶指针，boti为第为第i个堆栈个堆栈的栈底指针。另设的栈底指针。另设botn+1为为n+1个栈底指个栈底指针集合。其中第针集合。其中第n+1个堆栈是虚设的，目的个堆栈是虚设的，目的是为了检测第是为了检测第n个栈栈满与否。个栈栈满与否。 多栈共享空间问题多栈共

23、享空间问题初始时初始时， boti=topi=i*(m/n) (0=i=n-1)botn=m当当m=15，n=5时：时：各元素陆续进栈后：各元素陆续进栈后：03691215m-1bot0top0bot1top1bot2top2bot3top3bot4top4bot5ab1d1 d2g03691215m-1bot0top1bot2bot3top3bot4bot5top4top2bot1top0初始时初始时， boti=topi=i*(m/n) (0=i=n-1)botn=m当当m=15，n=5时：时：各元素陆续进栈后：各元素陆续进栈后：03691215m-1bot0top0bot1top1bot

24、2top2bot3top3bot4top4bot5abc1d1d2gg03691215m-1bot0top1bot2bot3top3bot4bot5top4top2bot1top0u第第i个堆栈个堆栈“栈空栈空”的条件是的条件是 topi=boti，(0=i=n-1)u第第i个堆栈个堆栈“栈满栈满”的条件是的条件是 topi=boti+1 (0=i=n-1)u在第在第i个栈中插入一个元素时，若个栈中插入一个元素时，若 topi-1=boti成立，则第成立，则第i个栈满，但个栈满，但m个空间个空间未必满。在第未必满。在第j个栈与第个栈与第j+1个栈之间可能还有可用个栈之间可能还有可用空间。给新元

25、素找到一个合适的位置，有三种情空间。给新元素找到一个合适的位置，有三种情况：况： 在在ijn中确定有中确定有1个可用空间的最小个可用空间的最小j，即找到，即找到的第的第i个栈右边的第一个可用空间的栈个栈右边的第一个可用空间的栈j，此时必有，此时必有topjbotj+1，然后将第，然后将第i+1，i+2，第，第j个栈个栈的所有元素连同栈指针都右移一个位置，使得第的所有元素连同栈指针都右移一个位置，使得第i个栈空出一个空间。个栈空出一个空间。 当第当第i个栈右边没有可用空间时，在个栈右边没有可用空间时，在0=ji中确定由可用空间的最大中确定由可用空间的最大j，即找，即找到第到第i个栈左边第个栈左边

26、第1个可用空间个可用空间j，然后将，然后将第第j+1，j+2，第，第i个栈的所有元素连个栈的所有元素连同栈指针都左移一个位置，使得第同栈指针都左移一个位置，使得第i个栈个栈空出一个空间。空出一个空间。 若查找完所有的堆栈，都没有发现自若查找完所有的堆栈，都没有发现自由空间，表明整个空间全被占用，即真由空间，表明整个空间全被占用，即真正产生了正产生了“溢出溢出”。u 多栈共享空间可以节省空间，但往往多栈共享空间可以节省空间，但往往要移动大量的数据元素。要移动大量的数据元素。n链式栈的定义链式栈的定义n链式栈类的定义链式栈类的定义n链栈中典型成员函数的实现链栈中典型成员函数的实现 链式栈链式栈 链

27、式栈的定义链式栈的定义n链式栈就是用一个线性链表来实现一个堆栈链式栈就是用一个线性链表来实现一个堆栈结构。栈中每个元素用一个链结点表示，同结构。栈中每个元素用一个链结点表示，同时，设置一个指针变量，指出当前栈顶元素时，设置一个指针变量，指出当前栈顶元素所在结点的存储位置，当栈为空时，有所在结点的存储位置，当栈为空时，有top=NULL，下图就是链接栈的一般形式：，下图就是链接栈的一般形式： 链栈的特点链栈的特点n链表的头结点就是栈顶元素的结点；链表的头结点就是栈顶元素的结点；n根据堆栈的定义，新结点的插入和栈顶根据堆栈的定义，新结点的插入和栈顶结点的删除都在表头进行结点的删除都在表头进行 ；插

28、入一个新元素，相当于在第一个结点之前插入一个新元素，相当于在第一个结点之前插入一个新结点；插入一个新结点； 删除链接栈的栈顶元素，就是删除链表的第删除链接栈的栈顶元素，就是删除链表的第一个结点。一个结点。n不会有栈满而产生溢出的问题。不会有栈满而产生溢出的问题。 链式栈类的定义链式栈类的定义n定义一个结点结构：定义一个结点结构：templatestruct StackNode /定义一个结点模板结构定义一个结点模板结构 type data; /结点的数据元素值结点的数据元素值 StackNode *next; /指向下一结点的指针指向下一结点的指针；链式栈类的定义：链式栈类的定义：链栈模板链栈

29、模板template /定义一个栈类模板定义一个栈类模板class LinkStack: public abstack protected: StackNode*top; /栈顶指针栈顶指针 /复制函数，将堆栈复制函数，将堆栈g复制给本链式栈复制给本链式栈 LinkStack & Copy(LinkStack & s); public: LinkStack( ); /无参构造函数无参构造函数 LinkStack(LinkStack & g) /拷贝构造函数拷贝构造函数 top=NULL; Copy(g); LinkStack( ) /析构函数，调用析构函数，调用Clear( )函数释函数释 C

30、lear( ); 放内存空间放内存空间 void Clear( ); /清空当前栈中元素清空当前栈中元素 void Push(type & x)； /进栈函数进栈函数 bool Pop(type & x)； /出栈函数出栈函数 /重载赋值运算符，用于同类型栈对象的赋值重载赋值运算符，用于同类型栈对象的赋值 LinkStack & operator=(LinkStack & g) Copy(g); return *this; ; 链栈中典型成员函数的实现链栈中典型成员函数的实现n构造函数构造函数n复制函数复制函数n清栈函数清栈函数n进栈函数进栈函数n出栈函数出栈函数 构造函数构造函数 初始化数据

31、成员值，构造一个空栈。初始化数据成员值，构造一个空栈。templateLinkStack: LinkStack( ) height=0; top=NULL;复制函数复制函数：将堆栈：将堆栈g中的内容复制给当前栈。中的内容复制给当前栈。 复制前，若当前栈非空，则清空，释放当前栈复制前，若当前栈非空，则清空，释放当前栈的结点所占的内存空间，并将当前栈高设置为的结点所占的内存空间，并将当前栈高设置为g栈栈高；复制时，首先分配一个栈顶结点，将栈栈高；复制时，首先分配一个栈顶结点，将g栈顶元素赋给新栈顶结点，然后循环进行其他各栈顶元素赋给新栈顶结点，然后循环进行其他各结点元素的赋值，至栈底结束。结点元素

32、的赋值，至栈底结束。 具体赋值过程：分配新结点，将具体赋值过程：分配新结点，将g栈结点数据栈结点数据元素值赋给新结点，将新结点链接到当前链式栈，元素值赋给新结点，将新结点链接到当前链式栈，将当前链式栈指针后移，同时将将当前链式栈指针后移，同时将g栈指针后移，栈指针后移，重复操作。重复操作。templateLinkStack& LinkStack:Copy(LinkStack &g) StackNode*p,*q,*r; /定义三个结点指针定义三个结点指针 if(top) Clear( ); /若当前栈非空则清栈若当前栈非空则清栈 height=g.height; /设置当前栈的栈高设置当前栈的

33、栈高 top=NULL; if(!g.top) return *this; /若若g为空栈返回为空栈返回 top=new StackNode; /为栈顶结点分配内存空间为栈顶结点分配内存空间 assert(top); /分配失败，设置出错信息，返回分配失败，设置出错信息，返回 top-next=NULL; top-data=g.top-data;/将数据的栈顶元素赋给当前栈顶将数据的栈顶元素赋给当前栈顶 q = g.top-next; /q指向指向g的栈顶下一个元素的栈顶下一个元素 p = top; /p指向当前栈顶指向当前栈顶while(q) /循环复制其它结点循环复制其它结点 r=new

34、StackNode; /分配新结点分配新结点 assert(r); /分配失败，设置出错信息，返回分配失败，设置出错信息，返回 r-data=q-data; /将栈将栈g第二个元素值赋给新结点第二个元素值赋给新结点 r-next=NULL; /r是当前栈的最后一个元素是当前栈的最后一个元素 p-next=r; /将新结点链到当前栈底，将新结点链到当前栈底，p指向栈底指向栈底 p=p-next; /当前链栈指针后移一个结点当前链栈指针后移一个结点 q=q-next; /g链式栈指针后移一个结点链式栈指针后移一个结点 return *this; 清栈函数清栈函数 释放链式栈中各结点元素所占的存储空

35、间。循环释放链式栈中各结点元素所占的存储空间。循环调用调用Pop()函数，删除当前栈顶结点，直到栈空为止。函数，删除当前栈顶结点，直到栈空为止。templateviod LinkStack:Clear( ) type x; while(Pop(x); /循环调用循环调用Pop( )函数，出栈，函数，出栈， 直到栈空为止直到栈空为止进栈函数进栈函数：将：将x压入堆栈中压入堆栈中 若栈非空，分配一个新结点，将新结点数据元素值设为若栈非空，分配一个新结点，将新结点数据元素值设为x，新结点插入链式栈前端，即栈顶元素，修改栈顶指针，新结点插入链式栈前端，即栈顶元素，修改栈顶指针指向新结点；若为空栈，分配

36、一个新结点，将其设为栈顶，指向新结点；若为空栈，分配一个新结点，将其设为栈顶，栈顶数据元素值设为栈顶数据元素值设为x。成功插入结点后，栈高加。成功插入结点后，栈高加1。templateviod LinkStack:Push(type & x) StackNode*p; if(top) /若栈非空若栈非空 p=new StackNode; /为为x分配一个结点分配一个结点n assert(p); /内存内存分配失败，设置出错信息，返回分配失败，设置出错信息，返回p-data=x; /将将x赋给结点数据元素赋给结点数据元素 p-next=top;/将结点插入链式栈前端，成为栈顶元素将结点插入链式栈

37、前端，成为栈顶元素 top=p; /修改栈顶指针修改栈顶指针 else /若为空栈若为空栈 top=new StackNode; /为栈顶元素分配内存为栈顶元素分配内存 assert(top); /分配失败，设置出错信息，返回分配失败，设置出错信息，返回 top-data=x; /将将x赋给栈顶数据元素赋给栈顶数据元素 top-next=NULL; height+; /栈高加栈高加1 出栈函数出栈函数 用于弹出栈顶元素，并将栈顶结点的数据元素值赋给用于弹出栈顶元素，并将栈顶结点的数据元素值赋给x。若栈非空，将栈顶结点的数据元素值赋给。若栈非空，将栈顶结点的数据元素值赋给x，保留栈，保留栈顶指针

38、，将其赋给顶指针，将其赋给p，将栈顶指针指向下一结点，删除，将栈顶指针指向下一结点，删除原栈顶结点原栈顶结点p，同时将栈高减，同时将栈高减1。templatebool LinkStack:Pop(type& x) StackNode*p; if(height) /若栈中有元素若栈中有元素 x=top-data; /将栈顶结点的数据元素赋给将栈顶结点的数据元素赋给x p=top; /将栈顶指针赋给将栈顶指针赋给p top=top-next; /修改栈顶指针，下移一个位置修改栈顶指针，下移一个位置 delete p; /删除原栈顶结点删除原栈顶结点 height-; /栈高减栈高减1 return

39、 true; return false; 11.4 堆栈应用举例堆栈应用举例n数制转换数制转换 在计算机中，常需要将十进制的数转换为在计算机中，常需要将十进制的数转换为其他进制的数，或将其他进制的数转换为其他进制的数，或将其他进制的数转换为十进制的数，将十进制数转换为其他进制十进制的数，将十进制数转换为其他进制数的基本方法是辗转相除法。数的基本方法是辗转相除法。例如：要将十进制数例如：要将十进制数1348转换为转换为8进制数，进制数， 运算过程如下：运算过程如下：NN/8N%81348 1684168 21021 252 02十进制十进制1348对应的八进制数是对应的八进制数是2504。计算顺

40、序计算顺序输出顺序输出顺序计算时从低位计算时从低位到高位顺序产到高位顺序产生八进制数的生八进制数的各个数位各个数位输出显示时按输出显示时按从高位到低位从高位到低位的顺序输出的顺序输出1 1）问题的提出）问题的提出从键盘一次性输入一串算术表达式，给出计算结果。从键盘一次性输入一串算术表达式，给出计算结果。2+32+3* *(5-4)=5(5-4)=511.4堆栈应用举例堆栈应用举例2 2）表达式的构成）表达式的构成 操作数操作数+ +运算符运算符+ +界符界符1 12 23 34 4如何确定运算符的运算顺序？如何确定运算符的运算顺序？常数常数+ +、- -、* *、/ /( )( )、# #11

41、.4 堆栈应用举例堆栈应用举例3 3）表达式的求值）表达式的求值： 例：例：5+65+6 (1+2)-4(1+2)-4 按照四则运算法则，上述表达式的计算过程为：按照四则运算法则，上述表达式的计算过程为： 5+65+6 (1+2)-4 = 5+6(1+2)-4 = 5+6 3-4 = 5+18-4 = 23-4 = 193-4 = 5+18-4 = 23-4 = 194 4）运算符优先关系表）运算符优先关系表 表达式中任何相邻运算符表达式中任何相邻运算符 1 1、 2 2 的优先关系有：的优先关系有： 1 1 2 2： 1 1的优先级的优先级 高于高于 2 2+ 2 1 - -* */( ()

42、 )#+- -* */( () )#=注：注：1 1、2 2是相邻算符，是相邻算符，1 1在左，在左，2 2在右在右11.4 堆栈应用举例堆栈应用举例5 5）算符优先算法）算符优先算法从左向右扫描表达式：从左向右扫描表达式： 遇操作数遇操作数保存；保存； 遇运算符号遇运算符号 j j与前面的刚扫描过的运算符与前面的刚扫描过的运算符 i i比较：比较： 若若 i i j j 则保存则保存 j j（因此已保存的运算符的优先关系为（因此已保存的运算符的优先关系为 1 1 2 2 3 3 j j 则说明则说明 i i是已扫描的运算符中优先级最高者，可进是已扫描的运算符中优先级最高者，可进行运算行运算

43、若若 i i= = j j 则说明括号内的式子已计算完，需要消去括号则说明括号内的式子已计算完，需要消去括号 5 + 4 (1 + 2) - 6后面也许有优先级后面也许有优先级更高的算符更高的算符+ +(后保存的算符优先级高后保存的算符优先级高用两个栈分别保存扫描过程中用两个栈分别保存扫描过程中遇到的操作数和运算符遇到的操作数和运算符11.4 堆栈应用举例堆栈应用举例 在算符优先算法中，建立了两个工作栈。一个是在算符优先算法中，建立了两个工作栈。一个是OPTROPTR栈，用以保存栈，用以保存运算符运算符；一个是；一个是OPNDOPND栈，用以保存栈，用以保存操作数操作数或运算或运算结果结果。算

44、法的基本思想是：算法的基本思想是： 1 1、首先置、首先置操作数栈操作数栈为空栈，表达式起始符为空栈，表达式起始符“# #”为为运算符栈运算符栈的栈底元素。的栈底元素。 2 2、依次读入表达式中每个字符，若是操作数，则、依次读入表达式中每个字符，若是操作数，则进进OPNDOPND栈；若是运算符，则与栈；若是运算符，则与OPTROPTR栈的栈顶运算符比栈的栈顶运算符比较优先级后作相应操作。较优先级后作相应操作。 直至整个表达式求值完毕（即直至整个表达式求值完毕（即OPTROPTR栈的栈顶元素栈的栈顶元素和当前读入的字符均为和当前读入的字符均为“# #”）。）。11.4 堆栈应用举例堆栈应用举例表达式求值示意：表达式求值示意：5 + 6 5 + 6 ( 1 + 2 ) - 4( 1 + 2 ) - 4totop pbasebaseOPTROPTR栈栈# #OPNDOPND栈栈totop pbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2