数据结构与算法（C++版）课件第3章 栈和队列

第3章栈和队列数据结构与算法

(C++版)(第2版)栈和队列是限定插入和删除只能在表的“端点”进行的线性表。栈和队列是两种常用的线存表3.1栈(stack)一、栈的基本概念只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶

(top)，另一端称为栈底(bottom)特点后进先出(LIFO)1.栈的概念与特点出栈入栈a1anan-1

topbottom（1）intLength()const

初始条件：栈已存在。

操作结果：返回栈元素个数。

（2）boolEmpty()const

初始条件：栈已存在。

操作结果：如栈为空，则返回true，否则返回false

（3）voidClear()

初始条件：栈已存在。

操作结果：清空栈。2.栈的基本操作（4）voidTraverse(void(*visit)(

constElemType&))const

初始条件：栈已存在。

操作结果：从栈底到栈顶依次对栈的每个元素调用函数(*visit)

（5）boolPush(constElemType&e)

初始条件：栈已存在。

操作结果：插入元素e为新的栈顶元素。

a1a2ane……栈底（6）boolTop(ElemType&e)const

初始条件：栈已存在且非空。

操作结果：用e返回栈顶元素。

a1a2an……栈底（7）boolPop(ElemType&e)

初始条件：栈已存在且非空。

操作结果：删除栈顶元素，并用e返回栈顶元素。a1a2anan-1

……栈底（8）boolPop()

初始条件：栈已存在且非空。

操作结果：删除栈顶元素。a1a2anan-1

……栈底二、栈的数组表示

——顺序栈在顺序实现中，利用数组依次存放从栈底到栈顶的数据元素用count存储数组中存储的栈的实际元素个数当count=0时表示栈为空入栈操作时，如栈未满，操作成功，count的值将加1出栈时，如栈不空，操作成功，并且count的值将减1//顺序栈类模板template<classElemType>classSqStack{protected://顺序栈的数据成员:

ElemType*elems; //元素存储空间

intmaxSize; //栈最大元素个数 intcount; //元素个数public://抽象数据类型方法声明及重载编译系统默认方法声明: SqStack(intsize=DEFAULT_SIZE);

//构造函数模板

virtual~SqStack(); //析构函数模板

intLength()const; //求栈长度

boolEmpty()const; //判断栈是否为空

voidClear(); //将栈清空

voidTraverse(void(*visit)(constElemType&)) const; //遍历栈

boolPush(constElemType&e); //入栈

boolTop(ElemType&e)const; //返回栈顶

boolPop(ElemType&e); //出栈

boolPop(); //出栈

SqStack(constSqStack<ElemType>&source); //复制构造函数模板

SqStack<ElemType>&operator=( constSqStack<ElemType>&source);

//重载赋值运算符};复制构造函数模板template<classElemType>SqStack<ElemType>::SqStack( constSqStack<ElemType>&source)//操作结果：由栈source构造新栈——复制构造函数模板{ maxSize=source.maxSize; //最大元素个数 elems=newElemType[maxSize];//分配存储空间 count=source.count; //栈元素个数 for(inttemPos=1;temPos<=Length();temPos++) { //从栈底到栈顶复制栈source的每个元素 elems[temPos-1]=source.elems[temPos-1]; }}template<classElemType>SqStack<ElemType>&SqStack<ElemType>::operator= (constSqStack<ElemType>&source)//操作结果：将栈source赋值给当前栈——重载赋值运算符{ if(&source!=this) { maxSize=source.maxSize; //最大元素个数 delete[]elems; //释放存储空间 elems=newElemType[maxSize];//分配存储空间 count=source.count; //复制栈元素个数 for(inttemPos=1;temPos<=Length();Pos++) { //从栈底到栈顶复制栈source的每个元素 elems[temPos-1]=source.elems[temPos-1]; } } return*this;}

top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop双栈共享一个栈空间三、链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈入栈和出栈操作都非常简单，一般都不使用头结点直接实现1.链式栈的基本概念//链栈类模板template<classElemType>classLinkStack{protected://链栈实现的数据成员: Node<ElemType>*top; //栈顶指针 intcount; //元素个数public://抽象数据类型方法声明及重载编译系统默认方法声明: LinkStack(); //无参数的构造函数

virtual~LinkStack(); //析构函数

intLength()const; //求栈长度2.链式栈的类模板 boolEmpty()const; //判断栈是否为空

voidClear(); //将栈清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍历栈

boolPush(constElemType&e); //入栈

boolTop(ElemType&e)const; //返回栈顶元素

boolPop(ElemType&e); //出栈

boolPop(); //出栈

LinkStack(constLinkStack<ElemType>&source); //复制构造函数模板

LinkStack<ElemType>&operator=(const LinkStack<ElemType>&source);//重载赋值};template<classElemType>LinkStack<ElemType>::LinkStack()//操作结果：构造一个空栈表{ top=NULL; //构造栈顶指针 count=0; //初始化元素个数}template<classElemType>LinkStack<ElemType>::~LinkStack()//操作结果：销毁栈{ Clear();}3.部分成员函数模板的实现template<classElemType>boolLinkStack<ElemType>::Push( constElemType&e)//操作结果：将元素e追加到栈顶,如成功则返加true,否则如动// 态内存已耗尽将返回false{ Node<ElemType>*newTop= newNode<ElemType>(e,top); if(newTop==NULL) { //动态内存耗尽 returnfalse; //失败 } else { //操作成功 top=newTop; count++; //入栈成功后元素个数加1 returntrue; //成功 }}template<classElemType>boolLinkStack<ElemType>::Pop(ElemType&e)//操作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,// 返回true,否则返回false{ if(Empty()) { //栈空 returnfalse; //失败 } else { //操作成功 Node<ElemType>*oldTop=top; //旧栈顶 e=oldTop->data; //用e返回栈顶元素 top=oldTop->next; //top指向新栈顶 deleteoldTop; //删除旧栈顶 count--; //出栈成功后元素个数自减1 returntrue; //功能 }}template<classElemType>boolLinkStack<ElemType>::Top(ElemType&e)const//操作结果：如栈非空,用e返回栈顶元素,返回true,否则// 返回false{ if(Empty()) { //栈空 returnfalse; //失败 } else { //栈非空,操作成功 e=top->data; //用e返回栈顶元素 returntrue; //成功 }}template<classElemType>voidLinkStack<ElemType>::Traverse(void(*visit)( constElemType&))const//操作结果：从栈底到栈顶依次对栈的每个元素调用函// 数(*visit){ Node<ElemType>*temPtr; //临时指针变量 LinkStack<ElemType>temS; //临时栈,temS中元素

//顺序与当前栈元素顺序相反 for(temPtr=top;temPtr!=NULL; temPtr=temPtr->next) { //用temPtr依次指向当前栈的每个元素 temS.Push(temPtr->data);

//对当前栈的每个元素入栈到temS中 }

for(temPtr=temS.top;temPtr!=NULL; temPtr=temPtr->next) { //用temPtr从依次指向栈temS的每个元素 (*visit)(temPtr->data);

//对栈temS的每个元素调用函数(*visit) }}3.2队列一、队列(Queue)的基本概念1.队列的初步认识定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)a1

a2

a3

anfrontrear

（1）intLength()const

初始条件：队列已存在。

操作结果：返回队列长度

（2）boolEmpty()const

初始条件：队列已存在。

操作结果：如队列为空，则返回true，否则返回false

（3）voidClear()

初始条件：队列已存在。

操作结果：清空队列2.队列的基本操作（4）voidTraverse(void(*visit)(

constElemType&))const

初始条件：队列已存在。

操作结果：依次对队列的每个元素调用函数(*visit)

（5）boolOutQueue(ElemType&e)

初始条件：队列非空。

操作结果：删除队头元素，并用e返回其值。

a1a2an……

队头队尾（6）boolOutQueue()

初始条件：队列非空。

操作结果：删除队头元素。

（7）boolGetHead(ElemType&e)const

初始条件：队列非空。

操作结果：用e返回队头元素。

a1a2an……队头队尾（8）boolInQueue(constElemType&e)

初始条件：队列已存在。

操作结果：插入元素e为新的队尾。a1a2ane……队头队尾二、链队列1.链队列的基本概念链式队列在入队时无队满问题，但有队空问题。队空条件为front==rear//链队列类模板template<classElemType>classLinkQueue{protected://链队列实现的数据成员:

Node<ElemType>*front,*rear;//队头队尾指针

intcount; //元素个数public://抽象数据类型方法声明及重载编译系统默认方法声明:

LinkQueue();

//无参数的构造函数模板

virtual~LinkQueue();

//析构函数模板2.链队列的类模板

intLength()const;

//求队列长度

boolEmpty()const;

//判断队列是否为空

voidClear();

//将队列清空

voidTraverse(void(*Visit)(constElemType&)) const;

//遍历队列

boolOutQueue(ElemType&e); //出队操作

boolOutQueue(); //出队操作

boolGetHead(ElemType&e)const; //取队头操作

boolInQueue(constElemType&e); //入队

LinkQueue(constLinkQueue<ElemType>&source); //复制构造函数模板

LinkQueue<ElemType>&operator=(const LinkQueue<ElemType>&source);//重载赋值};三、循环队列——队列的

顺序存储结构1.顺序队列的入队和出队frontrear空队列frontrearA入队AfrontrearB入队ABfrontrearC,D入队ABCDfrontrearA出队BCDfrontrearB出队CDfrontrearE,F,G入队CDEFGCDEFGfrontrearH入队,溢出队列的实际可用空间还没有使用完，这种情况下再插入一个新元素产生的溢出称主“假溢出”2.顺序队列的入队和出队原则

入队时将新元素按

rear指示位置加入再将队尾rear自加1:rear=rear+1。

出队时将下标为

front的元素取出,再将队头front自加1:front=front+1。

队满时再入队将溢出出错；队空时再出队将队空处理。解决假溢出方法：将队列元素存放数组首尾相接，形成循环(环形)队列。

队列存放数组被当作首尾相接的表处理。队头front、队尾rear自加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头front自加1:front=(front+1)%maxSize;队尾rear自加1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：count==0;队满条件：count==maxSize。 3.循环队列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空队列A入队B,C入队0123456701234567A出队B出队01234567D,E,F,G,H,I入队frontBCrearAfrontBCrearfrontCrearDEFGHI4.循环队列入队和出队示意图//循环队列类模板template<classElemType>classCircQueue{protected:

ElemType*elem; //元素存储空间 intfront,rear; //队头队尾

intmaxSize; //队列最大元素个数

intcount; //元素个数public://抽象数据类型方法声明及重载编译系统默认方法声明:

CircQueue(intsize=DEFAULT_SIZE);

//构造函数模板

virtual~CircQueue(); //析构函数模板5.循环队列的类模板

intLength()const; //求队列长度

boolEmpty()const; //判断队列是否为空

voidClear(); //将队列清空

voidTraverse(void(*visit)(constElemType&))const; //遍历队列

boolOutQueue(ElemType&e); //出队操作

boolOutQueue(); //出队操作

boolGetHead(ElemType&e)const; //取队头操作

boolInQueue(constElemType&e); //入队

CircQueue(constCircQueue<ElemType>&source); //复制构造函数模板

CircQueue<ElemType>&operator=(const CircQueue<ElemType>&source); //重载赋值运算符};template<classElemType>voidCircQueue<ElemType>::Traverse(void(*visit)( constElemType&))const//操作结果：依次对队列的每个元素调用函数(*visit){ for(inttemPos=front;temPos!=rear; temPos=(temPos+1)%maxSize) { //对队列的每个元素调用函数(*visit) (*visit)(elems[temPos]); }}6.部分成员函数模板的实现template<classElemType>boolCircQueue<ElemType>::OutQueue(ElemType&e)//操作结果：如果队列非空，那么删除队头元素，并用e// 返回其值，返回true,否则返回false{ if(!Empty()) { //队列非空 e=elems[front]; //用e返回队头元素 front=(front+1)%maxSize; //front指向下一元素 count--; //出队成功后元素个数自减1 returntrue; //成功 } else { //队列为空 returnfalse; //失败 }}template<classElemType>boolCircQueue<ElemType>::InQueue( constElemType&e)//操作结果：如果队列已满，返回false否则插入元素e为// 新的队尾，返回true{ if(count==maxSize) { //队列已满 returnfalse; //失败 } else { //队列未满，入队成功 elems[rear]=e; //插入e为新队尾 rear=(rear+1)%maxSize;//rear指向新队尾 count++; //入队成功后元素个数加1 returntrue; //成功 }}*3.3实例研究——表达式求值一、表达式基础一个表达式由操作数(亦称运算对象)、操作符

(亦称运算符)和分界符组成。算术表达式有三种表示：中缀(infix)表示

<操作数><操作符><操作数>，如A+B；前缀(prefix)表示

<操作符><操作数><操作数>，如+AB；后缀(postfix)表示

<操作数><操作数><操作符>，如AB+；二、表达式的中缀表示

表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。算符优先法就是根据上面的运算符优先关系来实现对表达式进行编译执行任何表达式都可看成由操作数（operand）、操作符（operator）和界限符（delimiter）组成为简单起见，只讨论算要四则运算符（“+”、“-”、“*”、“/”），操作数为常数，界限符为左右圆括和等号（“（”，“）”，“=”）；三、算符优先法对于任意两个操作符theta1和theta2的优先关系如下：theta1<theta2：theta1优先级低于theta2。theta1=theta2：theta1优先级等于theta2。theta1>theta2：theta1优先级高于theta2。theta1etheta2：theta1与theta2不允许相继出现。四、操作符的优先级操作符优先级相等的情况只出现在括号配对或左右操作符都是'='的情形。五、中缀算术表达式求值算法使用两个栈，操作符栈optr(operator)，操作数栈opnd(operand)，对中缀表达式求值的一般规则：在optr栈中压入一个'='

。从输入流获取一字符ch。取出optr的栈顶optrTop。当optrTop!='='或ch!='='

时,循环执行以下工作,否则结束算法。此时在opnd栈的栈顶得到运算结果。

while(optrTop!='='

||ch!='

='

){

①若ch不是操作符，则将字符放回输入流(cin.putback)，读操作数operand并进opnd栈，并读入下一字符送入ch；②若ch是操作符，将比较ch的优先级和optrTop的优先级：