数据结构第3章

数据结构A·第3章第3章堆栈和队列

引言堆栈和队列也是最常见的数据结构，在算法设计中经常使用，它们在逻辑上同线性表一样，都是线性结构，差别在于：线性表可以在表的任意位置插入和删除元素，而堆栈和队列只能在表的端点插入和删除元素。第3章堆栈和队列内容提要

1、定义堆栈与队列抽象数据类型

2、讨论堆栈与队列的顺序表示方法

3、讨论堆栈与队列的链接表示方法

4、以表达式计算为例讨论堆栈的应用

5、介绍递归的概念和递归算法3.1堆栈a0a1…ai…an-1入栈出栈bottomtop

图3-1栈的示意图堆栈（简称栈）的示意图S=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.1堆栈抽象数据类型

堆栈是后进先出（LastInFirstOut——LIFO）的动态线性数据结构。

1.堆栈的定义堆栈工作的演示ACB3.1堆栈3.1.1堆栈抽象数据类型

同时，堆栈也是是后进先出（LastInFirstOut——LIFO）的动态线性数据结构。

1.堆栈的定义ACB堆栈工作的演示3.1堆栈3.1.1堆栈抽象数据类型

ADTStack{数据:0个或多个元素的线性序列（a0,a1,...,an-1),其最大允许长度为ＭaxStackSize。其插入和删除运算都限制在同一端进行，并遵循LIFO原则。运算:Create()：建立一个空栈。

Destroy()：撤消一个栈。

IsEmpty()：若栈空，则返回true;否则返回false。

IsFull()：若栈满，则返回true;否则返回false。

Top(x)：返回栈顶元素。若操作成功，则返回true;否则返回false。

Push(x)：在栈顶插入元素x。

Pop()：从栈中删除栈顶元素。

Clear():清除堆栈中全部元素。}

2.栈的抽象数据类型3.1堆栈3.1.1堆栈抽象数据类型

3.栈的C++模板抽象类程序3-1堆栈的C++类#include<iostream.h>template<classT>classStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1堆栈3.1.2栈的顺序表示

1.栈的顺序表示法an-1a1a0topn-110栈s图3-2顺序栈maxTop………一维数组s存储栈中元素，maxTop+1为最大允许容量，top指示栈顶，top==-1表示空栈,top==maxTop表示栈满。

S=(a0,a1,…,an-1)3.1堆栈3.1.2栈的顺序表示

2.顺序栈类template<classT>classSeqStack:publicStack<T>{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//总是指向栈顶元素

intmaxTop;T*s;}an-1a1a0topn-110栈s图3-2顺序栈maxTop………3.1堆栈3.1.2栈的顺序表示

3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………template<classT>classSeqStack:publicStack<T>{public:……private:intmaxTop;inttop;T*s;}3.1堆栈3.1.2栈的顺序表示

3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………构造函数template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析构函数SeqStack<T>::~SeqStack(intMaxSize){delete[]s;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（1）取栈顶元素template<classT>boolSeqStack<T>::Top(T&x)const{if(IsEmpty()){//空栈处理

cout<<"Empty"<<endl;returnfalse;}x=s[top];returntrue;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（2）进栈（压入）template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){//溢出处理

cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………（3）出栈（弹出）template<classT>boolSeqStack<T>::Pop(){if(IsEmpty()){//空栈处理

cout<<"Underflow"<<endl;returnfalse;}top--;returntrue;}3.1堆栈3.1.3栈的链接表示

1.栈的链接表示法（链式栈）链式栈的定义和操作的实现类似于单链表。an-1a0…top∧图3-3链式栈

an-2an-3不带表头结点的单链表课堂提要第3章堆栈和队列3.1堆栈

3.1.1栈抽象数据类型

3.1.2栈的顺序表示

3.1.3栈的链接表示3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.3栈的链接表示

2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈

an-2an-3入栈操作push(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=top;top=q;3.1堆栈3.1.3栈的链接表示

2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈

an-2an-3出栈操作Pop()Node<T>*q=top;top=top->link;deleteq;3.2队列3.1.3栈的链接表示课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归队列的示意图

Q=(a0,a1,…,an-1)a0a1…an-1frontrear入队出队3.2队列3.2.1队列抽象数据类型

1.队列的定义队列是限定在表的一端插入，在表的另一端删除的线性数据结构。若队列中无元素，则为空队列队尾——允许插入元素的一端队头——允许删除元素的另一端Q=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归3.2队列3.2.1队列抽象数据类型

1.队列的定义a0a1…an-1frontrear入队出队若给定队列Q=(a0,a1,…,an-1)，则称a0是队头元素，an-1是队尾元素。元素a0,…,an-1依次入队，出队的顺序与入队相同，a0出队后，a1才能出队，因此又称队列为先进先出（FirstInFirstOut——FIFO）的动态线性数据结构。3.2队列3.2.1队列抽象数据类型

1.队列的定义ACBrearfront队列工作的演示(入队)3.2队列3.2.1队列抽象数据类型

1.队列的定义rearfront队列工作的演示(出队)ACB3.2队列3.2.1队列抽象数据类型

2.队列的抽象数据类型ADTQueue{

数据:0个或多个元素的线性序列（a0,a1,…,an-1),其最大长度为MaxQueueSize。它插入在一端进行，而删除在另一端进行，并遵循FIFO原则。运算:Create()：建立一个空队列。

Destroy()：撤消一个队列。

IsEmpty()：若队列空，则返回true;否则返回false。

IsFull()：若队列满，则返回true;否则返回false。

Front(x)：在x中返回队头元素。操作成功返回true；否则返回false。

EnQueue(x)：在队尾插入元素x。操作成功返回true；否则返回false。

DeQueue()：从队列中删除队头元素。操作成功返回true；否则返回falseClear():清除队列中全部元素。}3.2队列3.2.1队列抽象数据类型

3.队列的C++模板抽象类template<classT>classQueue{public:Queue(){};~Queue(){}; virtualboolEnQueue(constTx)=0;virtualboolDeQueue()=0;virtualboolFront(T&x)=0; virtualboolIsEmpty()const=0; virtualboolIsFull()const=0;virtualvoidClear()=0; };3.2队列3.2.2队列的顺序表示

1.队列的顺序表示法课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归01234=maxSize-1(a)空队列fr

图中f为front,r为rear3.2队列3.2.2队列的顺序表示

1.队列的顺序表示法

从(d)可以看到，当再有元素需要入队时将产生“溢出”，然而队列中尚有三个空元素单元，我们称这种现象为“假溢出”。指针f指向队首元素的前一个位置，指针r指向队尾元素50403020(b)元素20，30，40，50入队01234=maxSize-1fr50(c)元素20，30，40依次出队01234=maxSize-1fr50(d)元素60入队01234=maxSize-1fr603.2队列3.2.2队列的顺序表示

2.循环队列表示法

把数组从逻辑上看成是一个头尾相连的环。（a）空队列满队列front==rear实际仍有一个元素的空间未使用0fr12340f123420304050r3.2队列3.2.2队列的顺序表示

2.循环队列表示法注意r值的变化：

4+1=>00f123420304050r（b）元素20，30，40，50入队列（c）元素20，30，40出队列0f123450r（d）元素60，70入队列0f123450r60703.2队列3.2.2队列的顺序表示

2.循环队列表示法

实现循环队列操作：

(1)为使入队和出队实现循环，可以利用取余运算符%。

(2)队头指针进一：

front=(front+1)%maxSize；

(3)队尾指针进一：

rear=(rear+1)%maxSize；

(4)空队列：当front==rear时为空队列，

(5)满队列：当(rear+1)%maxSize==front时为满队列。满队列时实际仍有一个元素的空间未使用。3.2队列3.2.2队列的顺序表示

3.顺序队列类template<classT>classSeqQueue:publicQueue<T>{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}

boolIsEmpty()const；

boolIsFull()const；

boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};0fr12343.2队列3.2.2队列的顺序表示

4.动态一维数组描述顺序队列类template<classT>classSeqQueue:publicQueue<T>{public:……

private:intfront,rear;intmaxSize;T*q;}01…n-1…maxSize-1frontrearq……3.2队列3.2.2队列的顺序表示

4.动态一维数组描述顺序队列类01…n-1…maxSize-1frontrearq……构造函数template<classT>SeqQueue<T>::SeqQueue(intmSize){//生成一个空队列

maxSize=mSize;q=newT[maxSize];front=rear=0;}析构函数~SeqQueue(){delete[]q;}3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::IsEmpty()const{returnfront==rear;}template<classT>boolSeqQueue<T>::IsFull()const{return(rear+1)%maxSize==front;}（1）判空（2）判满3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::Front(T&x){if(IsEmpty()){cout<<"empty"<<endl;returnfalse;}x=q[(front+1)%maxSize];returntrue;}（3）取队列元素0f123420304050r3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::EnQueue(Tx){if(IsFull()){cout<<"Full"<<endl;returnfalse;}q[(rear=(rear+1)%maxSize)]=x;returntrue;}（4）进队列（插入）0f123420304050r元素50入队列0f1234203040r3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::DeQueue(){if(IsEmpty()){cout<<"Underflow"<<endl;returnfalse;}front=(front+1)%maxSize;returntrue;}（5）出队列（删除）0f123420304050r0f123450r

元素20，30，40出队列3.2队列3.2.3队列的链接表示队列的链接表示法（链式队列）链式队列的定义和操作的实现类似于单链表。课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归不带表头结点的单链表a0an-1…front∧图3-3链式队列

a1a2rear3.2队列3.2.3队列的链接表示队列的链接表示法（链式队列）a0an-1…front∧图3-3链式队列

a1a2rear入队列EnQueue(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=NULL;rear->link=q;rear=q;出队列DeQueue()Node<T>*q=front;front=front->link;delq;3.3堆栈的应用—表达式计算3.3.1表达式课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归

表达式：表达式习惯的书写形式是一个双目运算符位于两个操作数之间，如a＋b;还有单目运算符，如I++和-a。条件运算符是C/C++语言中惟一的三目运算符。

中缀表达式：操作符在两个操作数之间的表达式,如：a/(b-c)+d*e

前缀表达式：操作符放在两个操作数之前的表达式,如：+/a-bc*de

后缀表达式：操作符放在两个操作数之后的表达式（逆波兰表达式）如：abc-/de*+3.3堆栈的应用—表达式计算逆波兰式（ReversePolishnotation，RPN）

J.Lukasiewicz

19293.3堆栈的应用—表达式计算3.3.1表达式表3-1C++中部分操作符的优先级操作符优先级-,!7*,/,%6+,-5<,<=,>,>=4==,!=3&&2||1

有括号时先计算括号号中的表达式；高优先级先计算同级操作符计算：从左到右，或从右到左3.3堆栈的应用—表达式计算3.3.2后缀表达式求值比较中缀表达式及其对应的后缀表达式的例子表3.2中缀表达式和后缀表达式中缀表达式后缀表达式a*b+cab*c+a*b/cab*c/a*b*c*d*e*fab*c*d*e*f*a+(b*c+d)/eabc*d+e/+a*((b+c)/(d-e)-f)abc+de-/f-*a/(b-c)+d*eabc-/de*+课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归3.3堆栈的应用—表达式计算3.3.2后缀表达式求值后缀表达式求值优点：1）无界限符；2）求值时无需考虑操作符的优先级。因此用后缀表达式求值计算简便，在编译程序中常用。利用栈很容易计算后缀表达式的值。为了方便算法的实现，在后缀表达式的后面，通常会加上1个后缀表达式的结束符“＃”。3.3堆栈的应用—表达式计算3.3.2后缀表达式求值后缀表达式求值算法:

（1）从左往右顺序扫描后缀表达式；（2）遇到操作数就进栈；（3）遇到操作符就从栈中弹出两个操作数，执行该操作符规定的运算；并将结果进栈；（4）重复上述操作，直到表达式结束。弹出栈顶元素即为结果。

3.3堆栈的应用—表达式计算3.3.2后缀表达式求值642-/32*+#栈操作遇到结束符，弹出栈顶元素9即为结果#96、3出栈，计算3+6，结果9进栈+632、3出栈，计算3*2，结果6进栈*2332进栈2333进栈332、6出栈，计算6/2，结果3进栈/262、4出栈，计算4-2，结果2进栈-2462进栈264

6扫描项表3.3后缀表达式的计算6进栈64进栈43.3堆栈的应用—表达式计算3.3.2后缀表达式求值642-/32*+#6-24/32*+#642=22利用栈计算后缀表达式值的演示3.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示233642-/32*+#6-24/32*+#=3263.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示33642-/32*+#6-24/32*+#=2663.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示63=642-/32*+#6-24/32*+#9=9==>6/(4-2)+3*26

4

2

-

/

3

2

*

+=93.3堆栈的应用—表达式计算3.3.2后缀表达式求值在Linux系统中有后缀表达式计算器。$>dc43+p73.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器假设该计算器可以接收后缀表达式，但只进行+、-、*、/和^运算。为实现计算器，定义一个计算器类。程序3.5计算器类#include”SeqStack.h”#include<math.h>classCalculator{public:Calculator(intmaxSize):s(maxSize){};//构造函数

voidRun();voidClear(s.Clear();)private:SeqStack<double>s;//私有数据成员是一个栈，用于存放操作数

voidPushOperand(double);//操作数进栈

boolGetOperands(double&,double&);//两个操作数出栈

voidDoOperator(char);//操作符进行处理（遇到操作符时调用）};3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器成员函数的实现：voidCalculator::PushOperand(doubleop){s.Push(op);//操作数进栈}BOOLCalculator::GetOperands(double&op1,double&op2){//两个操作数出栈

if(!s.Top(op1)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();if(!s.Top(op2)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();returntrue;}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器voidCalculator::DoOperator(charoper)//遇到操作符时调用{boolresult;doubleoper1,oper2;result=GetOperands(oper1,oper2);//从栈中弹出2个操作数3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器if(result)//执行操作符oper指定的运算

switch(oper)//根据操作符做相应的运算，先出栈的操作数oper1{//放在操作符的右边，后出栈的oper2放在左边

case'+':s.Push(oper2+oper1);break;case'-':s.Push(oper2-oper1);break;case'*':s.Push(oper2*oper1);break;case'/':if(fabs(oper1)<1e-6){//如果分母为0，则做出错处理

cerr<<"Divideby0!"<<endl; Clear();} elses.Push(oper2/oper1);break;case'^':s.Push(pow(oper2,oper1));break;}elseClear();}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器voidCalculator::Run(){charc;doublenewop;while(cin>>c,c!='#'){//从输入流试读入一个字符，遇结束符结束

switch(c){//读入的字符做如下处理

case'+':case'-':case'*':case'/':case'^':DoOperator(c);break;//是操作符则进行相应的计算

default:cin.putback(c);//如不是操作符，则将试读入的字符放回输入流

cin>>newop;//读入一个操作数

PushOperand(newop);break;//操作数进栈

}}if(s.Top(newop))cout<<newop<<endl;//取栈顶元素，得结果输出}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例：模拟一个简单的计算器计算器类的应用程序：#include“calculator.h”constintSIZE=20;voidmain(){CalculatorCal(SIZE);Cal.Run();}输入：642-/32*+#结果：93.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式注意：只考虑左结合的双目运算。每个表达式以“＃”号作为其结束标记。输入中缀表达式由运算符、操作数、园括弧和‘＃’四种不同类型的项组成的序列输出后缀表达式课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式栈内优先级isp(in-stackpriority)栈外优先级icp(incomingpriority)对未进栈的左括号赋以最高优先级，对已进栈的左括号赋以最低优先级。假定表达式的语法正确性检查已在表达式转换之前完成。3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式转换步骤：（1）从左到右扫描中缀表达式，遇到#转（6）；否则继续；（2）遇到操作数直接输出；（不进栈）（3）遇到“）”，则连续出栈输出，直到遇到“（”为止（注意：“（”出栈但不输出）；（4）若是其它操作符，则与栈顶的操作符比较优先级；若小于栈顶操作符的栈内优先级，则连续出栈输出，直到大于等于栈顶操作符的栈内优先级结束，该操作符进栈；（5）转（1）继续；（6）输出栈中剩余操作符（#除外）。3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式a(/中缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+bc-)d+*e#3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式中缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+a(/bc-d+*e#3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式中缀表达式:a/(b-c