清華數(shù)據(jù)結(jié)構(gòu)課件

第四章棧和隊列棧表達(dá)式求值隊列優(yōu)先隊列只允許在一端插入和刪除的線性表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)棧(Stack)退棧進(jìn)棧a0an-1an-2topbottomtemplate<classType>classStack{ public:Stack(intsz

=10); //構(gòu)造函數(shù)

voidPush(Type&item);//進(jìn)棧

TypePop();//出棧

TypeGetTop();//取棧頂元素

voidMakeEmpty();//置空棧

intIsEmpty()const;//判棧空否

intIsFull()const;//判棧滿否}棧的抽象數(shù)據(jù)類型#include<assert.h>template<classType>classStack{private:int

top; //棧頂指針

Type*elements; //棧元素數(shù)組

intmaxSize; //棧最大容量public:Stack(intsz

=10);//構(gòu)造函數(shù)

~Stack(){delete[]elements;

}

voidPush(Type

&item);//進(jìn)棧

棧的數(shù)組表示—順序棧TypePop();//出棧

TypeGetTop();//取棧頂

voidMakeEmpty(){top=-1;

}//置空棧

intIsEmpty()const{returntop==-1;

}

intIsFull()const{returntop==maxSize-1;

} }template<classType>Stack<Type>::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];

assert(elements!=NULL);//斷言}

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧ctopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptoptemplate<classType>voidStack<Type>::Push(Type

&item){

assert(!IsFull()); //先決條件斷言

elements[++top]=item;//加入新元素}template<classType>intstack<Type>::Pop(){if(IsEmpty())return0;//棧空不退棧

top--;return1;//退出棧頂元素}

template<classType>Typestack<Type>::GetTop(){assert(!IsEmpty()); //先決條件斷言

returnelements[top];//取出棧頂元素}

雙棧共享一個?？臻gb[0]t[0]t[1]b[1]0maxSize-1V棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作toptemplate<classType>classStack;template<classType>classStackNode{friendclassStack<Type>;private:

Typedata; //結(jié)點(diǎn)數(shù)據(jù)

StackNode<Type>*link;//結(jié)點(diǎn)鏈指針public:StackNode(Typed=0,StackNode<Type>*l=NULL):data(d),link(l){}};鏈?zhǔn)綏?LinkedStack)類的定義template<classType>classStack{private:StackNode<Type>*top;//棧頂指針public:Stack():top(NULL){}~Stack();

voidPush(constType

&item);//進(jìn)棧

intPop();//退棧

Type*GetTop();//讀取棧頂元素

voidMakeEmpty();//實(shí)現(xiàn)與~Stack()同

intIsEmpty(){returntop==NULL;

}}template<classType>Stack<Type>::~Stack(){StackNode<Type>*p;

while(top!=NULL)//逐結(jié)點(diǎn)回收

{p=top;top=top->link;

deletep;

}}template<classType>voidStack<Type>::Push(constType

&item){top=newStackNode<Type>(item,top);

//新結(jié)點(diǎn)鏈入*top之前,并成為新棧頂}template<classType>intStack<Type>::Pop(){if(IsEmpty())return0; StackNode<Type>*p=top;top=top->link; //修改棧頂指針

deletep;

return1;//釋放}template<classType>TypeStack<Type>::GetTop(){assert(!IsEmpty());

returntop->data;}

表達(dá)式求值一個表達(dá)式由操作數(shù)(亦稱運(yùn)算對象)、操作符

(亦稱運(yùn)算符)和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；表達(dá)式的中綴表示

a+b*

(c-d)-e^f/g表達(dá)式中相鄰兩個操作符的計算次序?yàn)椋簝?yōu)先級高的先計算；優(yōu)先級相同的自左向右計算；當(dāng)使用括號時從最內(nèi)層括號開始計算。rst1rst2rst3rst4rst5rst6C++中操作符的優(yōu)先級

優(yōu)先級

操作符

1 單目-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 一般表達(dá)式的操作符有4種類型：算術(shù)操作符如雙目操作符（+、-、*、/和%）以及單目操作符（-）。關(guān)系操作符包括<、<=、==、!=、>=、>。這些操作符主要用于比較。邏輯操作符如與(&&)、或(||)、非(!)。括號‘(’和‘)’它們的作用是改變運(yùn)算順序。應(yīng)用后綴表示計算表達(dá)式的值從左向右順序地掃描表達(dá)式，并用一個棧暫存掃描到的操作數(shù)或計算結(jié)果。在后綴表達(dá)式的計算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達(dá)式中不出現(xiàn)。計算例abcd-

*+ef^g/-rst1rst2rst3rst4rst5rst6通過后綴表示計算表達(dá)式值的過程順序掃描表達(dá)式的每一項(xiàng)，根據(jù)它的類型做如下相應(yīng)操作：若該項(xiàng)是操作數(shù)，則將其壓棧；若該項(xiàng)是操作符<op>，則連續(xù)從棧中退出兩個操作數(shù)Y和X，形成運(yùn)算指令X<op>Y，并將計算結(jié)果重新壓棧。當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計算結(jié)果。voidCalculator::Run(){charch;

doublenewoperand;while(cin>>ch,ch!=‘=’){switch(ch){

case‘+’:case‘-’:case‘*’:case‘/’:

DoOperator(ch);break;//計算

default:cin.putback(ch);

//將字符放回輸入流

cin>>newoperand;//讀操作數(shù)

AddOperand(newoperand);}}}利用棧將中綴表示轉(zhuǎn)換為后綴表示使用棧可將表達(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。為了實(shí)現(xiàn)這種轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級。各個算術(shù)操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對或棧底的“;”號與輸入流最后的“;”號配對時。中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法操作符棧初始化，將結(jié)束符‘;’進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。重復(fù)執(zhí)行以下步驟，直到ch=‘;’，同時棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個字符ch。若ch是操作符，判斷ch的優(yōu)先級icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級isp：若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號讀入下一個字符ch。算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。voidpostfix(expressione){stack<char>s;charch,op;s.Push(‘;’); cin.Get(ch);

while(!s.IsEmpty()&&ch!=';')

if(isdigit(ch))

{

cout<<ch;cin.Get(ch);}

else{

if(isp(s.GetTop())<icp(ch)){s.Push(ch);

cin.Get(ch);}

else

if(isp(s.GetTop())>icp(ch)){op=s.GetTop();s.Pop();cout<<op;} else{op=s.GetTop();s.Pop(); if(op==‘(’)cin.Get(ch);}}}

中綴算術(shù)表達(dá)式求值使用兩個棧，操作符棧OPTR(operator)，操作數(shù)棧OPND(operand)，對中綴表達(dá)式求值的一般規(guī)則：(1)建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個“;”(2)從頭掃描中綴表達(dá)式，取一字符送入ch。(3)當(dāng)ch!=“;”時,執(zhí)行以下工作,否則結(jié)束算法。此時在OPND棧的棧頂?shù)玫竭\(yùn)算結(jié)果。

①若ch是操作數(shù)，進(jìn)OPND棧，從中綴表達(dá)式取下一字符送入ch；②若ch是操作符，比較icp(ch)的優(yōu)先級和isp(OPTR)的優(yōu)先級：

若icp(ch)>isp(OPTR)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一字符送入ch；

若icp(ch)<isp(OPTR)，則從OPND棧退出a2和a1，從OPTR棧退出θ,形成運(yùn)算指令(a1)θ(a2)，結(jié)果進(jìn)OPND棧；

若icp(ch)==isp(OPTR)

且ch==

“)”，則從OPTR棧退出棧頂?shù)摹?”，對消括號，然后從中綴表達(dá)式取下一字符送入ch；隊列(

Queue)定義隊列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontreartemplate<classType>classQueue{

public:Queue(int=10);

//構(gòu)造函數(shù)

voidEnQueue(constType&item);//進(jìn)隊

TypeDeQueue();

//出隊列

TypeGetFront();

//取隊頭元素值

voidMakeEmpty();

//置空隊列

intIsEmpty()const;

//判隊列空否

intIsFull()const;

//判隊列滿否

}隊列的抽象數(shù)據(jù)類型隊列的進(jìn)隊和出隊

frontrear空隊列frontrearA進(jìn)隊AfrontrearB進(jìn)隊ABfrontrearC,D進(jìn)隊ABCDfrontrearA退隊BCDfrontrearB退隊CDfrontrearE,F,G進(jìn)隊CDEFGCDEFGfrontrearH進(jìn)隊,溢出隊列的進(jìn)隊和出隊原則

進(jìn)隊時隊尾指針先進(jìn)一

rear=rear+1，

再將新元素按

rear指示位置加入。

出隊時隊頭指針先進(jìn)一

front=front+1，再將下標(biāo)為

front的元素取出。

隊滿時再進(jìn)隊將溢出出錯；隊空時再出隊將隊空處理。解決辦法之一：將隊列元素存放數(shù)組首尾相接，形成循環(huán)(環(huán)形)隊列。

隊列存放數(shù)組被當(dāng)作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize-1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊頭指針進(jìn)1:front=(front+1)%maxSize;隊尾指針進(jìn)1:rear=(rear+1)%maxSize;隊列初始化：front=rear=0;隊空條件：front

==

rear;隊滿條件：(rear+1)%maxSize==front

循環(huán)隊列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空隊列A進(jìn)隊B,C進(jìn)隊0123456701234567A退隊B退隊01234567D,E,F,G,H進(jìn)隊frontBCrearAfrontBCrearfrontCrearDEFGH#include<assert.h>template<classType>classQueue{ private:

intrear,front;

//隊尾,隊頭指針

Type*elements; //隊列元素數(shù)組

intmaxSize;//最大元素個數(shù)public:Queue(int=10);~Queue(){delete[]elements;

}

voidEnQueue(constType

&item);

//進(jìn)隊循環(huán)隊列的類定義intDeQueue();//退隊

Type*GetFront();//取隊頭元素

voidMakeEmpty(){

front=rear=0;

}

intIsEmpty()const

{returnfront==rear;}

intIsFull()const{return(rear+1)%maxSize==front;}

intLength()const{return(rear-front+maxSize)%maxSize;}}template<classType>Queue<Type>::Queue(intsz):

front(0),rear(0),maxSize(sz){elements=newType[maxSize];

assert(elements!=NULL);}template<classType>voidQueue<Type>::EnQueue(constType

&item){

assert(!IsFull());

rear=(rear+1)%MaxSize; elements[rear]=item; }template<classType>intQueue<Type>::DeQueue(){

if(IsEmpty())return0; front=(front+1)%MaxSize;

return1;}template<classType>TypeQueue<Type>::GetFront(){

assert(!IsEmpty());

returnelements[(front+1)%MaxSize];}隊列的鏈接表示—鏈?zhǔn)疥犃嘘狀^在鏈頭，隊尾在鏈尾。鏈?zhǔn)疥犃性谶M(jìn)隊時無隊滿問題，但有隊空問題。隊空條件為front==NULLfrontreartemplate<classType>classQueue;template<classType>classQueueNode{ friendclassQueue<Type>;private:

Typedata; //隊列結(jié)點(diǎn)數(shù)據(jù)

QueueNode<Type>*link;//結(jié)點(diǎn)鏈指針public:QueueNode(Typed=0,QueueNode<Type>*l=NULL):data(d),link(l){}};

鏈?zhǔn)疥犃蓄惖亩xtemplate<classType>classQueue{

private:

QueueNode<Type>*front,*rear;

//隊頭、隊尾指針指針public:Queue():rear(NULL),front(NULL){}

~Queue();

voidEnQueue(constType

&item);intDeQueue();

Type*GetFront();

voidMakeEmpty();//實(shí)現(xiàn)與~Queue()同intIsEmpty()const

{returnfront==NULL;

}

};

template<classType>Queue<Type>::~Queue(){//隊列的析構(gòu)函數(shù)

QueueNode<Type>*p;

while(front!=NULL){

//逐個結(jié)點(diǎn)釋放

p=front;front=front->link;

deletep;}}template<classType>voidQueue<Type>::EnQueue(constType&item){//將新元素item插入到隊列的隊尾

if(front==NULL)//創(chuàng)建第一個結(jié)點(diǎn)

front=rear=newQueueNode

<Type>(item,NULL);

else

//隊列不空,插入

rear=rear->link=newQueueNode

<Type>(item,NULL);}template<classType>intQueue<Type>::DeQueue(){

if(IsEmpty())return0;//判隊空

QueueNode<Type>*p=front; front=front->link;

deletep;

return1; }template<classType>Type*Queue<Type>::GetFront(){if(IsEmpty())returnNULL;

return

&front->data;}

隊列的應(yīng)用舉例—

逐行打印二項(xiàng)展開式(a+b)i的系數(shù)分析第

i行元素與第i+1行元素的關(guān)系從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù)i=2i=3i=401331014641012100110sts+t從第i

行數(shù)據(jù)計算并存放第i+1行數(shù)據(jù)121013310

146s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+t

s+t

s+t

s+t

s+t

s+ts+ts+t利用隊列打印二項(xiàng)展開式系數(shù)的程序#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGVI(intn){Queueq;

//隊列初始化

q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);

ints=0;

for(

int

i=1;i<=n;i++){//逐行計算

cout<<endl; q.EnQueue(0);

for(intj=1;j<=i+2;j++){//下一行

intt=q.DeQueue(); q.EnQueue(s+t); s=t;

if(j!=i+2)cout<<s<<'';

}

}}優(yōu)先級隊列(PriorityQueue)優(yōu)先級隊列每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素如下表：任務(wù)優(yōu)先權(quán)及執(zhí)行順序的關(guān)系數(shù)字越小，優(yōu)先權(quán)越高#include<assert.h>#include<iostream.h>#include<stdli