数据结构 第3讲 栈和队列课件

第3章栈和队列栈和队列是限定插入和删除只能在表的“端点”进行的线性表。栈和队列是两种常用的数据类型栈1．intLength()const

初始条件：栈已存在。

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

2．boolEmpty()const

初始条件：栈已存在。

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

3．voidClear()

初始条件：栈已存在。

操作结果：清空栈。

4．voidTraverse(void(*visit)(constElemType&))const

初始条件：栈已存在。

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

5．StatusCodePush(constElemType&e)

初始条件：栈已存在。

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

a1a2ane……6．StatusCodeTop(ElemType&e)const

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

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

a1a2an……7．StatusCodePop(ElemType&e)

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

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

……//顺序栈类模板template<classElemType>classSqStack{protected://顺序栈的数据成员: intcount; //元素个数 intmaxSize; //栈最大元素个数 ElemType*elems; //元素存储空间//辅助函数模板: boolFull()const; //判断栈是否已满 voidInit(intsize); //初始化栈复制构造函数模板template<classElemType>SqStack<ElemType>::SqStack(constSqStack<ElemType>©)//操作结果：由栈copy构造新栈——复制构造函数模板{ elems=NULL; //未分配存储空间前,elems为空 Init(copy.maxSize); //初始化新栈 count=copy.count; //栈元素个数 for(intcurPosition=1;curPosition<=Length(); curPosition++) { //从栈底到栈顶对栈copy的每个元素进行复制 elems[curPosition-1]= copy.elems[curPosition-1]; }}

top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop

双栈共享一个栈空间b[0]t[0]t[1]b[1]0maxSize-1V栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头top链式栈(LinkedStack)类模板的定义 boolEmpty()const; //判断栈是否为空 voidClear(); //将栈清空 voidTraverse(void(*visit)(constElemType&)) const; //遍历栈 StatusCodePush(constElemType&e); //入栈 StatusCodeTop(ElemType&e)const;

//返回栈顶元素 StatusCodePop(ElemType&e); //出栈 LinkStack(constLinkStack<ElemType>©);

//复制构造函数模板 LinkStack<ElemType>&operator=(const LinkStack<ElemType>©);//重载赋值};template<classElemType>LinkStack<ElemType>::LinkStack()//操作结果：构造一个空栈表{ Init();}template<classElemType>LinkStack<ElemType>::~LinkStack()//操作结果：销毁栈{ Clear();}template<classElemType>StatusCodeLinkStack<ElemType>::Pop(ElemType&e)//操作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,// 返回SUCCESS,否则返回UNDER_FLOW{ if(Empty()) { //栈空 returnUNDER_FLOW; } else { //操作成功 Node<ElemType>*old_top=top; //旧栈顶 e=old_top->data; //用e返回栈顶元素 top=old_top->next; //top指向新栈顶 deleteold_top; //删除旧栈顶 returnSUCCESS; }}template<classElemType>StatusCodeLinkStack<ElemType>::Top(ElemType&e) const//操作结果：如栈非空,用e返回栈顶元素,返回// SUCCESS,否则返回UNDER_FLOW{ if(Empty()) { //栈空 returnUNDER_FLOW; } else { //栈非空,操作成功 e=top->data; //用e返回栈顶元素 returnSUCCESS; }}表达式求值一个表达式由操作数(亦称运算对象)、操作符

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

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

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

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

表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。C++中操作符的优先级

优先级

操作符

7 单目+、-、！6 *、/、% 5 +、-

4 <、<=、>、>=3==、!= 2 && 1 ||

中缀表达式中各个算术操作符的优先级Isp叫做栈内(instackpriority)优先数Icp叫做栈外(incomingpriority)优先数。栈内运算符实际上是表达式中左边的运算符,栈外运算符是表达式中右边的运算符。操作符优先数相等的情况只出现在括号配对或栈底的‘=’号与输入流最后的‘=’号配对时。中缀算术表达式求值中缀算术表达式求值使用两个栈，操作符栈OPTR(operator)，操作数栈OPND(operand)，对中缀表达式求值的一般规则：(1)在OPTR栈中压入一个‘=’。(2)从输入流获取一字符ch。(3)取出OPTR的栈顶OPTR_top。(4)当OPTR_top!=‘=’或ch!=‘=’时,循环执行以下工作,否则结束算法。此时在OPND栈的栈顶得到运算结果。

while(OPTR_top!=‘=’

||ch!=‘=’){

①若ch是数字字符或小数点,

则ch一个操作数的开始字符，将字符放回输入流(cin.putback)，读操作数newoperand并进OPND栈，并读入下一字符送入ch；②否则若ch是操作符，比较Icp(ch)的优先级和Isp(OPTR_top)的优先级：

若Isp(OPTR_top)<Icp(ch)，则ch进OPTR栈，从中缀表达式取下一字符送入ch；

否则若Isp(OPTR_top)>Icp(ch)，则从OPND栈退出a2和a1，从OPTR栈退出θ,形成运算指令(a1)θ(a2)，结果进OPND栈；

否则若Isp(OPTR_top)==Icp(ch)且ch==

“)”，则从OPTR栈退出栈顶的“(”，对消括号，然后从中缀表达式取下一字符送入ch。

③否则既不是操作符也不是操作数，表示有非法字符。

④取出OPTR的栈顶OPTR_top。}队列队列(

Queue)定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)a1

a2

a3

anfrontrear1．intLength()const

初始条件：队列已存在。

操作结果：返回队列长度

2．boolEmpty()const

初始条件：队列已存在。

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

3．voidClear()

初始条件：队列已存在。

操作结果：清空队列4．voidTraverse(void(*visit)(constElemType&))const

初始条件：队列已存在。

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

5．StatusCodeOutQueue(ElemType&e)

初始条件：队列非空。

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

a1a2an……

6．StatusCodeGetHead(ElemType&e)const

初始条件：队列非空。

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

a1a2an……7．StatusCodeInQueue(constElemType&e)

初始条件：队列已存在。

操作结果：插入元素e为新的队尾。a1a2ane……队列的链接表示—链式队列

队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==rear//链队列类模板template<classElemType>classLinkQueue{protected://链队列实现的数据成员: Node<ElemType>*front,*rear;//队头队尾指指//辅助函数模板: voidInit(); //初始化队列public://抽象数据类型方法声明及重载编译系统默认方法声明: LinkQueue(); //无参数的构造函数模板 virtual~LinkQueue(); //析构函数模板 intLength()const; //求队列长度

boolEmpty()const; //判断队列是否为空 voidClear(); //将队列清空 voidTraverse(void(*visit)(constElemType&)) const; //遍历队列 StatusCodeOutQueue(ElemType&e);//出队操作 StatusCodeGetHead(ElemType&e)const;

//取队头操作 StatusCodeInQueue(constElemType&e);//入队 LinkQueue(constLinkQueue<ElemType>©);

//复制构造函数模板 LinkQueue<ElemType>&operator=(const LinkQueue<ElemType>©);//重载赋值};顺序队列的进队和出队frontrear空队列frontrearA进队AfrontrearB进队ABfrontrearC,D进队ABCDfrontrearA退队BCDfrontrearB退队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出队列的进队和出队原则

进队时将新元素按

rear指示位置加入再将队尾指针先进一rear=rear+1。

出队时将下标为

front的元素取出,再将队头指针先进一front=front+1。

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

01234567front01234567front01234567frontrearAABCrearrear空队列A进队B,C进队0123456701234567A退队B退队01234567D,E,F,G,H,I进队frontBCrearAfrontBCrearfrontCrearDEFGHI队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front

==

rear;队满条件：(rear+1)%maxSize

==front

循环队列(CircularQueue)//循环队列类模板template<classElemType>classSqQueue{protected: intfront,rear; //队头队尾 intmaxSize; //队列最大元素个数 ElemType*elem; //元素存储空间//辅助函数模板: boolFull()const; //判断队列是否已满 voidInit(); //初始化队列public://抽象数据类型方法声明及重载编译系统默认方法声明: SqQueue(intsize=DEFAULT_SIZE);//构造函数模板 virtual~SqQueue(); //析构函数模板 intLength()const; //求队列长度 boolEmpty()const; //判断队列是否为空 voidClear(); //将队列清空 voidTraverse(void(*visit)(constElemType&)) const; //遍历队列 StatusCodeOutQueue(ElemType&e);//出队操作 StatusCodeGetHead(ElemType&e)const;

//取队头操作 StatusCodeInQueue(constElemType&e);//入队 SqQueue(constSqQueue<ElemType>©);

//复制构造函数模板 SqQueue<ElemType>&operator=(const SqQueue<ElemType>©);//重载赋值运算符};template<classElemType>boolSqQueue<ElemType>::Full()const//操作结果：如队列已满，则返回true，否则返回false{ returnLength()==maxSize-1;}template<classElemType>voidSqQueue<ElemType>::Init()//操作结果：初始化队列{ rear=front=0;}template<classElemType>intSqQueue<ElemType>::Length()const//操作结果：返回队列长度 { return(rear-front+maxSize)%maxSize;}template<classElemType>voidSqQueue<ElemTy