DS04_堆栈与队列1

1、第6章堆栈与队列（一）SIE. BITSIE. BIT引入栈和队列引入栈和队列1234某些现实的抽象某些现实的抽象SIE. BITSIE. BIT 栈和队列是操作受限操作受限的线性表； 通常称，栈和队列是限定插入插入和和删除删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列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栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型SIE. BITSIE. BIT栈栈- -主要

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

3、空栈； 堆栈的插入运算简称为堆栈的插入运算简称为入栈或进入栈或进栈栈，删除运算简称为，删除运算简称为出栈或退栈出栈或退栈。出栈出栈进栈进栈栈的示意图栈的示意图栈顶栈顶栈底栈底a an na a2 2a a1 1SIE. BITSIE. BIT 堆栈的特点出栈出栈进栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底第一个进栈的元素在栈底最后一个进栈的元素在栈顶最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元最后一个出栈的元素为栈底元素素栈的示意图栈的示意图栈顶栈顶栈底栈底a an na a2 2a a1 1SIE. BITSIE.

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

5、当前栈是否为满，栈满时，不能进行入：测试当前栈是否为满，栈满时，不能进行入栈运算。上溢。栈运算。上溢。SIE. BITSIE. BIT2 栈的抽象类定义template/定义一个抽象的模板堆栈类定义一个抽象的模板堆栈类classabstackpublic:boolIsEmpty()/判断堆栈是否为空判断堆栈是否为空return(height=0)?true:false;/进栈函数，将一元素压入栈中进栈函数，将一元素压入栈中virtualvoidPush(type&)=0;/出栈函数，从栈中取一元素出栈函数，从栈中取一元素virtualboolPop(type&)=0;/清栈函数

6、，用于释放栈所占的内存空间清栈函数，用于释放栈所占的内存空间virtualvoidClear()=0;protected:unsignedheight;/栈高栈高SIE. BITSIE. BIT（1）抽象栈类中定义了栈高抽象栈类中定义了栈高height，可简化操作，例如判断栈空、，可简化操作，例如判断栈空、栈满。栈满。height在在abstack类中为类中为protected，它的派生类可以访问它。，它的派生类可以访问它。在抽象栈的数据成员中没有栈顶指针，因为顺序栈和链栈的栈顶在抽象栈的数据成员中没有栈顶指针，因为顺序栈和链栈的栈顶指针具有不同的数据类型，顺序栈指针具有不同的数据类型，顺序栈

7、(整型整型)、链栈、链栈(指针型指针型)；（2）根据栈的常用操作，在根据栈的常用操作，在abstack类中定义了类中定义了4个函数，其中个函数，其中3个是个是纯虚函数，其实现与栈的存储结构有关，因此在派生类中给出其纯虚函数，其实现与栈的存储结构有关，因此在派生类中给出其定义。定义。IsEmpty();判定堆栈是否为空或栈高是否为判定堆栈是否为空或栈高是否为0；Push(type&);将将type类型的数据元素插入到栈顶；类型的数据元素插入到栈顶；Pop(type&);将栈顶元素弹出并赋给将栈顶元素弹出并赋给type类型的元素；类型的元素；Clear();将堆栈清空。将堆栈清空。

8、抽象栈类说明：SIE. BITSIE. BIT3 栈的定义及其实现 顺序栈的定义顺序栈的定义 顺序栈类的定义及典型成员函数顺序栈类的定义及典型成员函数的实现的实现 多栈共享空间问题多栈共享空间问题SIE. BITSIE. BIT 顺序栈的定义 设一维数组为设一维数组为STACKmaxsize; 再设一个再设一个整型变量整型变量top表示表示栈顶指针栈顶指针：当堆：当堆栈不空时，栈不空时，top的值就是栈顶元素的的值就是栈顶元素的下标值下标值；当堆栈为当堆栈为空空时，有时，有top=-1； top最大最大取值为取值为maxsize-1。 STACK0为第一个进入堆栈的元素，当为第一个进入堆栈的元

9、素，当没没有删除有删除运算时，运算时，STACKi-1为为第第i个个进入堆进入堆栈的元素，栈的元素，STACKtop为栈顶元素为栈顶元素M-1210toptopA AB BSATCKSIE. BITSIE. BIT 顺序栈的示意图toptoptoptopA AB BC CD DE E空栈空栈toptopA AA A进栈进栈B C D EB C D E进栈进栈toptopA AB BE D CE D C出栈出栈称为：栈满称为：栈满SIE. BITSIE. BIT顺序栈的定义 堆栈是动态结构，存在堆栈是动态结构，存在溢出问题溢出问题。当堆栈中已经。当堆栈中已经有有maxsize个元素时，如果再做进

10、栈运算就会产生个元素时，如果再做进栈运算就会产生溢出，称之为溢出，称之为上溢上溢；对空栈进行删除运算也会产；对空栈进行删除运算也会产生溢出，称之为生溢出，称之为下溢下溢。 为了避免溢出，在对堆栈进行进栈运算和退栈运为了避免溢出，在对堆栈进行进栈运算和退栈运算之前都应该分别测试堆栈算之前都应该分别测试堆栈“是否已满是否已满”或者或者“是否已空是否已空”。SIE. BITSIE. BIT 顺序栈类的定义template /定义一个顺序栈类模板定义一个顺序栈类模板classSeqStack:pubilcabstackpublic:SeqStack(inti);/构造函数，构造函数，i用来设置栈的最大

11、高度用来设置栈的最大高度SeqStack(SeqStack&s)/拷贝构造函数，用于同类型栈的赋值拷贝构造函数，用于同类型栈的赋值copy(s);SeqStack()/析构函数，调用析构函数，调用Clear()函数释放栈所函数释放栈所Clear();占的内存空间占的内存空间voidPush(type&x);/进栈进栈:将元素将元素x压入栈中压入栈中boolPop(type&x);/出栈出栈:将栈顶元素值放入将栈顶元素值放入x中中SIE. BITSIE. BIT/清栈函数，用于释放栈所占的内存空间清栈函数，用于释放栈所占的内存空间voidClear()deleteelem

12、ents;SeqStack&Copy(SeqStack&s);/拷贝函数拷贝函数:同类型栈赋值同类型栈赋值/重载赋值运算符重载赋值运算符“”，用于同类型栈赋值，用于同类型栈赋值SeqStack&operator=(SeqStack&s)deleteelements;Copy(s);return*this;boolIsFull();/判断栈是否为满判断栈是否为满return(top=maxsize-1)?true:false;/top=maxsize-1为关系表达式为关系表达式protected:inttop;/栈顶指针栈顶指针type*elements;/一维数

13、组指针，用于存放栈中元素一维数组指针，用于存放栈中元素intmaxsize;/栈的最大高度栈的最大高度;SIE. BITSIE. BIT(1)增加了三个数据成员，增加了三个数据成员， top栈顶指针，是整数下标；栈顶指针，是整数下标；elements是指针变量，存放栈元素，在构造函数中对其是指针变量，存放栈元素，在构造函数中对其进行初始化；进行初始化；maxsize表示栈的最大高度，顺序栈的栈表示栈的最大高度，顺序栈的栈高不能超过高不能超过maxsize，否则会溢出；，否则会溢出；(2)定义了两个构造函数，一个带缺省参数，初始化顺序定义了两个构造函数，一个带缺省参数，初始化顺序栈类中数据成员的

14、值，栈类中数据成员的值，height0，top-1，建空栈。，建空栈。另一个是拷贝构造函数，将另一个同类型的顺序栈原另一个是拷贝构造函数，将另一个同类型的顺序栈原版拷贝到当前栈。析构函数版拷贝到当前栈。析构函数SeqStack()调用调用Clear()函数将堆栈清空。函数将堆栈清空。 顺序栈类定义说明：SIE. BITSIE. BIT 顺序栈类典型成员函数的实现 构造函数构造函数 进栈函数进栈函数 出栈函数出栈函数 拷贝函数拷贝函数SIE. BITSIE. BIT 构造函数 用于建立栈的对象，为栈的数据成员用于建立栈的对象，为栈的数据成员赋初值。赋初值。首先将栈高置为首先将栈高置为0，将栈顶指

15、针，将栈顶指针top置为置为-1，设置一个空栈；设置一个空栈；然后，根据参数值，设置最大栈高，并为然后，根据参数值，设置最大栈高，并为此栈分配内存空间。此栈分配内存空间。SIE. BITSIE. BITtemplateSeqStack:SeqStack(inti)height=0;top=-1;maxsize=i10?i:10;/最大栈高最小为最大栈高最小为10(如何改动？如何改动？)elements=newtypemaxsize;assert(elements!=0);SIE. BITSIE. BIT 进栈函数 首先测试堆栈是否已满。首先测试堆栈是否已满。若栈顶指针若栈顶指针top=maxs

16、ize-1，所有位置均已占满，若，所有位置均已占满，若再插入新元素，将产生溢出；再插入新元素，将产生溢出；若栈顶指针若栈顶指针topmaxsize-1，可以插入新元素；，可以插入新元素；先将栈顶指针先将栈顶指针top加加1，指到当前可加入新元素的位置，指到当前可加入新元素的位置，然后将新的元素插在此位置上，这个新插入的元素将然后将新的元素插在此位置上，这个新插入的元素将成为新的栈顶元素。成为新的栈顶元素。SIE. BITSIE. BIT 进栈函数0SIE. BITSIE. BITtemplate/函数模板函数模板voidSeqStack:Push(type&x)assert(!IsFu

17、ll();/栈满警告，出错处理栈满警告，出错处理elements+top=x;/将栈顶指针加将栈顶指针加1，将元素，将元素放入栈顶放入栈顶height+;/栈高加栈高加1 SIE. BITSIE. BIT 出栈函数 首先测试堆栈是否为空栈，若为空栈，出错首先测试堆栈是否为空栈，若为空栈，出错处理；否则返回栈顶元素的值，并将其保存处理；否则返回栈顶元素的值，并将其保存在在x中；中； 将栈顶指针减将栈顶指针减1。SIE. BITSIE. BIT 出栈函数0SIE. BITSIE. BITtemplateboolSeqStack:Pop(type&x)if(IsEmpty()/栈空警告，出错

18、处理栈空警告，出错处理returnfalse;elsex=elementstop;/取出栈顶元素，取出栈顶元素，将其值放入将其值放入x中中 top-;/栈顶指针减栈顶指针减1height-;/栈高减栈高减1returntrue; SIE. BITSIE. BIT 拷贝函数templateSeqStack&SeqStack:Copy(SeqStack&s)maxsize=s.maxsize;/设置最大栈高设置最大栈高elements=newtypemaxsize;/为本栈分配内存空间为本栈分配内存空间assert(elements);/分配失败，提出警告并进行出错处理分配失败，提

19、出警告并进行出错处理SIE. BITSIE. BITintlen=s.height;for(inti=0;ilen;i+)/从栈底至栈顶，依次将栈从栈底至栈顶，依次将栈s中的元素赋给本栈中的元素赋给本栈elementsi=*(s.elements+i);top=s.top;/设置新栈栈顶设置新栈栈顶height=s.height;/设置新栈栈高设置新栈栈高return*this;SIE. BITSIE. BIT 顺序栈的缺点 顺序栈保留着顺序存储的固有缺点，即在重新顺序栈保留着顺序存储的固有缺点，即在重新调整存储空间时，元素的移动量较大，尤其在调整存储空间时，元素的移动量较大，尤其在指定的存储

20、空间即将充满时，这种情况更为突指定的存储空间即将充满时，这种情况更为突出。出。SIE. BITSIE. BIT 多栈共享空间问题 有时在一个程序中，可能需要同时使用两个或多个有时在一个程序中，可能需要同时使用两个或多个堆栈。为了避免溢出，需要为每个堆栈分配一个足堆栈。为了避免溢出，需要为每个堆栈分配一个足够大的空间。但带来两个问题：够大的空间。但带来两个问题：1.各个堆栈所需的空间大小很难估计；各个堆栈所需的空间大小很难估计；2.由于堆栈是动态结构，各个堆栈的实际大小在使由于堆栈是动态结构，各个堆栈的实际大小在使用过程中都会发生动态变化，有时其中一个堆栈产用过程中都会发生动态变化，有时其中一个

21、堆栈产生了上溢，而其它堆栈还留有很多可用空间。生了上溢，而其它堆栈还留有很多可用空间。SIE. BITSIE. BIT 多栈共享空间问题 考虑多栈共享一个大的内存空间，要解决相应产生考虑多栈共享一个大的内存空间，要解决相应产生的问题。的问题。 设将多个堆栈顺序地映射到一个已知大小为设将多个堆栈顺序地映射到一个已知大小为m的存的存储空间储空间STACKm上。上。SIE. BITSIE. BIT 多栈共享空间问题1、两个堆栈共享两个堆栈共享该存储空间：第一个栈底位于该存储空间：第一个栈底位于STACK0，另一个栈底位于，另一个栈底位于STACKm-1。使用时。使用时两栈各自向中间伸展，仅当两个栈顶

22、指针相遇（两栈各自向中间伸展，仅当两个栈顶指针相遇（S1.top=S2.top）时才发生上溢。）时才发生上溢。aS10bS11cS124S233S222S211S20STACK0STACKm-1S1.topS2.topSIE. BITSIE. BIT2、两个以上堆栈共享两个以上堆栈共享该存储空间该存储空间(大小为大小为m)： 将将m个存储空间平均分配给个存储空间平均分配给n个栈，每个栈的存储个栈，每个栈的存储空间为空间为m/n。 设设topn为为n个堆栈的栈顶指针集合，个堆栈的栈顶指针集合，topi为第为第i个个堆栈的栈顶指针，堆栈的栈顶指针，boti为第为第i个堆栈的栈底指针。个堆栈的栈底指

23、针。另设另设botn+1为为n+1个栈底指针集合。其中第个栈底指针集合。其中第n+1个个堆栈是虚设的，目的是为了检测第堆栈是虚设的，目的是为了检测第n个栈栈满与否。个栈栈满与否。 多栈共享空间问题SIE. BITSIE. BIT初始时初始时，boti=topi=i*(m/n)(0=i=n-1)botn=m当当m=15，n=5时：时：各元素陆续进栈后各元素陆续进栈后： 03691215m-1bot0top0bot1top1bot2top2bot3top3bot4top4bot5abc1d1d2gg03691215m-1bot0top1bot2bot3top3bot4bot5top4top2bot

24、1top0SIE. BITSIE. BITu第第i个堆栈个堆栈“栈空栈空”的条件是的条件是topi=boti，(0=i=n-1)u第第i个堆栈个堆栈“栈满栈满”的条件是的条件是topi=boti+1(0=i=n-1)u多栈共享空间经过扩展，还可以节省多栈共享空间经过扩展，还可以节省空间，但往往要移动大量的数据元素。空间，但往往要移动大量的数据元素。SIE. BITSIE. BIT链式栈的定义链式栈的定义链式栈类的定义链式栈类的定义链栈中典型成员函数的实现链栈中典型成员函数的实现链式栈链式栈SIE. BITSIE. BIT 链式栈的定义 链式栈就是用一个线性链表来实现一个堆栈结构。链式栈就是用一

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

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

27、定义：链栈模板template/定义一个栈类模板定义一个栈类模板classLinkStack:publicabstackprotected:StackNode*top;/栈顶指针栈顶指针/复制函数，将堆栈复制函数，将堆栈g复制给本链式栈复制给本链式栈LinkStack&Copy(LinkStack&g);public:LinkStack();/无参构造函数无参构造函数LinkStack(LinkStack&g)/拷贝构造函数拷贝构造函数top=NULL;Copy(g);SIE. BITSIE. BITLinkStack()/析构函数，调用析构函数，调用Clear()函数

28、释放内存空间函数释放内存空间Clear();voidClear();/清空当前栈中元素清空当前栈中元素voidPush(type&x)；/进栈函数进栈函数boolPop(type&x)；/出栈函数出栈函数/重载赋值运算符，用于同类型栈对象的赋值重载赋值运算符，用于同类型栈对象的赋值LinkStack&operator=(LinkStack&g)Copy(g);return*this;SIE. BITSIE. BIT 链栈中典型成员函数的实现 构造函数构造函数 复制函数复制函数 清栈函数清栈函数 进栈函数进栈函数 出栈函数出栈函数SIE. BITSIE. BIT构

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

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

31、非空则清栈height=g.height;/设置当前栈的栈高设置当前栈的栈高top=NULL;if(!g.top)return*this;/若若g为空栈返回为空栈返回top=newStackNode;/为栈顶结点分配内存空间为栈顶结点分配内存空间assert(top);/分配失败，设置出错信息，返回分配失败，设置出错信息，返回top-next=NULL;top-data=g.top-data;/将数据的栈顶元素赋给当前栈顶将数据的栈顶元素赋给当前栈顶constLinkStack&gSIE. BITSIE. BITq=g.top-next;/q指向指向g的栈顶下一个元素的栈顶下一个元素p

32、=top;/p指向当前栈顶指向当前栈顶while(q)/循环复制其它结点循环复制其它结点r=newStackNode;/分配新结点分配新结点assert(r);/分配失败，设置出错信息，返回分配失败，设置出错信息，返回r-data=q-data;/将栈将栈g第二个元素值赋给新结点第二个元素值赋给新结点r-next=NULL;/r是当前栈的最后一个元素是当前栈的最后一个元素p-next=r;/将新结点链到当前栈底，将新结点链到当前栈底，p指向栈底指向栈底p=p-next;/当前链栈指针后移一个结点当前链栈指针后移一个结点q=q-next;/g链式栈指针后移一个结点链式栈指针后移一个结点retur

33、n*this;SIE. BITSIE. BIT 清栈函数清栈函数释放链式栈中各结点元素所占的存储空间。循环调释放链式栈中各结点元素所占的存储空间。循环调用用Pop()函数，删除当前栈顶结点，直到栈空为止。函数，删除当前栈顶结点，直到栈空为止。templateviodLinkStack:Clear()typex;while(Pop(x);/循环调用循环调用Pop()函数，出栈，函数，出栈，直到栈空为止直到栈空为止SIE. BITSIE. BIT 进栈函数进栈函数：将：将x压入堆栈中压入堆栈中若栈非空，分配一个新结点，将新结点数据元素值设为若栈非空，分配一个新结点，将新结点数据元素值设为x，新结点

34、，新结点插入链式栈前端，即栈顶元素，修改栈顶指针指向新结点；若为空插入链式栈前端，即栈顶元素，修改栈顶指针指向新结点；若为空栈，分配一个新结点，将其设为栈顶，栈顶数据元素值设为栈，分配一个新结点，将其设为栈顶，栈顶数据元素值设为x。成功。成功插入结点后，栈高加插入结点后，栈高加1。templateviodLinkStack:Push(type&x)StackNode*p;SIE. BITSIE. BITif(top)/若栈非空若栈非空p=newStackNode;/为为x分配一个结点分配一个结点nassert(p);/内存分配失败，设置出错信息，返回内存分配失败，设置出错信息，返回 p

35、-data=x;/将将x赋给结点数据元素赋给结点数据元素p-next=top;/将结点插入链式栈前端，成为栈顶元素将结点插入链式栈前端，成为栈顶元素top=p;/修改栈顶指针修改栈顶指针else/若为空栈若为空栈top=newStackNode;/为栈顶元素分配内存为栈顶元素分配内存assert(top);/分配失败，设置出错信息，返回分配失败，设置出错信息，返回top-data=x;/将将x赋给栈顶数据元素赋给栈顶数据元素top-next=NULL;height+;/栈高加栈高加1/问题：如何优化本函数？问题：如何优化本函数？SIE. BITSIE. BIT用于弹出栈顶元素，并将栈顶结点的数

36、据元素值赋给用于弹出栈顶元素，并将栈顶结点的数据元素值赋给x。若栈非。若栈非空，将栈顶结点的数据元素值赋给空，将栈顶结点的数据元素值赋给x，保留栈顶指针，将其赋给，保留栈顶指针，将其赋给p，将栈顶指针指向下一结点，删除原栈顶结点将栈顶指针指向下一结点，删除原栈顶结点p，同时将栈高减，同时将栈高减1。templateboolLinkStack:Pop(type&x)StackNode*p;if(height)/若栈中有元素若栈中有元素x=top-data;/将栈顶结点的数据元素赋给将栈顶结点的数据元素赋给xp=top;/将栈顶指针赋给将栈顶指针赋给ptop=top-next;/修改栈顶指

37、针，下移一个位置修改栈顶指针，下移一个位置deletep;/删除原栈顶结点删除原栈顶结点height-;/栈高减栈高减1returntrue;returnfalse;出栈函数出栈函数SIE. BITSIE. BIT4 堆栈应用举例 数制转换数制转换在计算机中，常需要将十进制的数转换为其他进在计算机中，常需要将十进制的数转换为其他进制的数，或将其他进制的数转换为十进制的数，制的数，或将其他进制的数转换为十进制的数，将十进制数转换为其他进制数的基本方法是辗转将十进制数转换为其他进制数的基本方法是辗转相除法。相除法。SIE. BITSIE. BIT例如：要将十进制数例如：要将十进制数1348转换为转换为8进制数，进制数，运算过程如下：运算过程如下：NN/8N%8134816841682102125202十进制十进制1348对应的八进制数是对应的八进制数是2504。计算顺序计算顺序输出顺序输出顺序计算时从低位计算时从低位到高位顺序产到高位顺序产生八进制数的生八进制数的各个数位各个数位输出显示时按输出显示时按从高位到低位从高位到低位的顺序输出的顺序输出SIE. BITSIE. BIT4 堆栈应用举例 迷宫问题迷宫问题: : 迷宫矩阵迷宫矩阵 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 0 1 0