73_栈与队列的基本操作及其应用

《73_栈与队列的基本操作及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C++程序设计7.3栈与队列的基本操作及应用东南大学VC++课程06级copyright:柏毅版本号：V2005.08-06.017.3栈与队列的基本操作及其应用栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。7.3.1栈7.3.3队　列7.3.2栈　的　应　用7.3.1栈栈定义为只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做栈顶(top)，而另一端叫栈底(bottom)。栈中没有任何元素时，称为空栈。进栈时最先进栈的在最下面，最后的在最上面，后来居上。而出栈时顺序相反，最后进栈的最先出栈，而最先进栈的最后出栈。所以栈又称作

2、后进先出的线性表。栈可以用顺序表实现，称顺序栈；也可以用链表实现，称链栈。参见下图，设给定栈s=(a0，a1，……，an-1)，称a0为栈底，an-1为栈顶。进栈时最先进栈的a0在最下面，an-1在最上面。而出栈时顺序相反，最后进栈的an-1最先出栈，而最先进栈的a0最后出栈。a0an-2……a1an-1bottom进栈toptoptoptoptop出栈图示为顺序栈。其中栈底bottom是指向栈数据区的下一单元，这样判断是否为空栈会更方便，只需top与bottom相同就是空栈。通常只有栈顶与操作有关。templateclassStack{inttop;//栈顶

3、指针（下标）T*elements;//动态建立的元素intmaxSize;//栈最大容纳的元素个数public:Stack(int=20);//构造函数，栈如不指定大小，设为20元素~Stack(){delete[]elements;}voidPush(constT&data);//压栈TPop();//弹出，top--TGetElem(inti);//取数据，top不变voidMakeEmpty(){top=-1;}//清空栈boolIsEmpty()const{returntop==-1;}//判栈空boolIsFull()const{returntop==maxSize-1;

4、}//判栈满voidPrintStack();};//输出栈内所有数据【例7.6】顺序栈的类模板定义：voidmain(){inti,a[10]={0,1,2,3,4,5,6,7,8,9},b[10];Stackistack(10);for(i=0;i<10;i++)istack.Push(a[i]);if(istack.IsFull())cout<<"栈满"<

5、<10;i++)cout<classNode{//链栈结点类模板Tinfo;Node*link;public:Node(Tdata=0,Node*next=NULL){info=data;link=next;}friendclassStack;};top……^……链栈templateclassStack{//链栈类模板Node*top;//栈顶指针public:Stac

6、k(){top=NULL;}~Stack();//析构函数voidPush(constT&data);//压栈TPop();//弹出TGetTop();//取栈顶元素voidMakeEmpty();//清空栈boolIsEmpty(){returntop==NULL;}};链栈类模板，无头结点链表7.3.2栈的应用（选读）顺序栈和链栈逻辑功能是一样，尽管这里两个栈模板的成员函数功能选择稍有出入，因为顺序栈可以随机访问其中的元素，而链栈只能顺序访问，但逻辑上完全可以做到一样（物理结构不同）。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，可能溢出。链栈内存空间随用随开，不会溢出

7、，但执行复杂（不断地动态分配），速度慢。栈可用于表达式的计算。现考虑最简单的+、-、*、/四个运算符和结束符＝组成的算术表达式，只有两个优先级，先*/，后+-。设有：a+b*c-d/e=；为实现运算符的优先级，采用两个栈：一个数栈，一个运算符栈。数栈暂存操作数，运算符栈暂存运算符。从左向右扫描算术表达式，遇到操作数，压入数栈；遇到运算符，则与运算符栈栈顶的运算符比较优先级，若新的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数字栈出栈的两个数据进行运算