數(shù)據(jù)結(jié)構(gòu)與算法（C++版）課件第3章 棧和隊(duì)列

第3章棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)與算法

(C++版)(第2版)棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。棧和隊(duì)列是兩種常用的線存表3.1棧(stack)一、棧的基本概念只允許在一端插入和刪除的線性表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)1.棧的概念與特點(diǎn)出棧入棧a1anan-1

topbottom（1）intLength()const

初始條件：棧已存在。

操作結(jié)果：返回棧元素個(gè)數(shù)。

（2）boolEmpty()const

初始條件：棧已存在。

操作結(jié)果：如棧為空，則返回true，否則返回false

（3）voidClear()

初始條件：棧已存在。

操作結(jié)果：清空棧。2.棧的基本操作（4）voidTraverse(void(*visit)(

constElemType&))const

初始條件：棧已存在。

操作結(jié)果：從棧底到棧頂依次對(duì)棧的每個(gè)元素調(diào)用函數(shù)(*visit)

（5）boolPush(constElemType&e)

初始條件：棧已存在。

操作結(jié)果：插入元素e為新的棧頂元素。

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

初始條件：棧已存在且非空。

操作結(jié)果：用e返回棧頂元素。

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

初始條件：棧已存在且非空。

操作結(jié)果：刪除棧頂元素，并用e返回棧頂元素。a1a2anan-1

……棧底（8）boolPop()

初始條件：棧已存在且非空。

操作結(jié)果：刪除棧頂元素。a1a2anan-1

……棧底二、棧的數(shù)組表示

——順序棧在順序?qū)崿F(xiàn)中，利用數(shù)組依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素用count存儲(chǔ)數(shù)組中存儲(chǔ)的棧的實(shí)際元素個(gè)數(shù)當(dāng)count=0時(shí)表示棧為空入棧操作時(shí)，如棧未滿，操作成功，count的值將加1出棧時(shí)，如棧不空，操作成功，并且count的值將減1//順序棧類模板template<classElemType>classSqStack{protected://順序棧的數(shù)據(jù)成員:

ElemType*elems; //元素存儲(chǔ)空間

intmaxSize; //棧最大元素個(gè)數(shù) intcount; //元素個(gè)數(shù)public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SqStack(intsize=DEFAULT_SIZE);

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

virtual~SqStack(); //析構(gòu)函數(shù)模板

intLength()const; //求棧長(zhǎng)度

boolEmpty()const; //判斷棧是否為空

voidClear(); //將棧清空

voidTraverse(void(*visit)(constElemType&)) const; //遍歷棧

boolPush(constElemType&e); //入棧

boolTop(ElemType&e)const; //返回棧頂

boolPop(ElemType&e); //出棧

boolPop(); //出棧

SqStack(constSqStack<ElemType>&source); //復(fù)制構(gòu)造函數(shù)模板

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

//重載賦值運(yùn)算符};復(fù)制構(gòu)造函數(shù)模板template<classElemType>SqStack<ElemType>::SqStack( constSqStack<ElemType>&source)//操作結(jié)果：由棧source構(gòu)造新?！獜?fù)制構(gòu)造函數(shù)模板{ maxSize=source.maxSize; //最大元素個(gè)數(shù) elems=newElemType[maxSize];//分配存儲(chǔ)空間 count=source.count; //棧元素個(gè)數(shù) for(inttemPos=1;temPos<=Length();temPos++) { //從棧底到棧頂復(fù)制棧source的每個(gè)元素 elems[temPos-1]=source.elems[temPos-1]; }}template<classElemType>SqStack<ElemType>&SqStack<ElemType>::operator= (constSqStack<ElemType>&source)//操作結(jié)果：將棧source賦值給當(dāng)前棧——重載賦值運(yùn)算符{ if(&source!=this) { maxSize=source.maxSize; //最大元素個(gè)數(shù) delete[]elems; //釋放存儲(chǔ)空間 elems=newElemType[maxSize];//分配存儲(chǔ)空間 count=source.count; //復(fù)制棧元素個(gè)數(shù) for(inttemPos=1;temPos<=Length();Pos++) { //從棧底到棧頂復(fù)制棧source的每個(gè)元素 elems[temPos-1]=source.elems[temPos-1]; } } return*this;}

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧ctopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptop雙棧共享一個(gè)棧空間三、鏈?zhǔn)綏ｆ準(zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^鏈?zhǔn)綏Ｈ霔：统鰲２僮鞫挤浅：?jiǎn)單，一般都不使用頭結(jié)點(diǎn)直接實(shí)現(xiàn)1.鏈?zhǔn)綏５幕靖拍?/鏈棧類模板template<classElemType>classLinkStack{protected://鏈棧實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*top; //棧頂指針 intcount; //元素個(gè)數(shù)public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: LinkStack(); //無(wú)參數(shù)的構(gòu)造函數(shù)

virtual~LinkStack(); //析構(gòu)函數(shù)

intLength()const; //求棧長(zhǎng)度2.鏈?zhǔn)綏５念惸０?boolEmpty()const; //判斷棧是否為空

voidClear(); //將棧清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍歷棧

boolPush(constElemType&e); //入棧

boolTop(ElemType&e)const; //返回棧頂元素

boolPop(ElemType&e); //出棧

boolPop(); //出棧

LinkStack(constLinkStack<ElemType>&source); //復(fù)制構(gòu)造函數(shù)模板

LinkStack<ElemType>&operator=(const LinkStack<ElemType>&source);//重載賦值};template<classElemType>LinkStack<ElemType>::LinkStack()//操作結(jié)果：構(gòu)造一個(gè)空棧表{ top=NULL; //構(gòu)造棧頂指針 count=0; //初始化元素個(gè)數(shù)}template<classElemType>LinkStack<ElemType>::~LinkStack()//操作結(jié)果：銷毀棧{ Clear();}3.部分成員函數(shù)模板的實(shí)現(xiàn)template<classElemType>boolLinkStack<ElemType>::Push( constElemType&e)//操作結(jié)果：將元素e追加到棧頂,如成功則返加true,否則如動(dòng)// 態(tài)內(nèi)存已耗盡將返回false{ Node<ElemType>*newTop= newNode<ElemType>(e,top); if(newTop==NULL) { //動(dòng)態(tài)內(nèi)存耗盡 returnfalse; //失敗 } else { //操作成功 top=newTop; count++; //入棧成功后元素個(gè)數(shù)加1 returntrue; //成功 }}template<classElemType>boolLinkStack<ElemType>::Pop(ElemType&e)//操作結(jié)果：如棧非空,刪除棧頂元素,并用e返回棧頂元素,// 返回true,否則返回false{ if(Empty()) { //?？? returnfalse; //失敗 } else { //操作成功 Node<ElemType>*oldTop=top; //舊棧頂 e=oldTop->data; //用e返回棧頂元素 top=oldTop->next; //top指向新棧頂 deleteoldTop; //刪除舊棧頂 count--; //出棧成功后元素個(gè)數(shù)自減1 returntrue; //功能 }}template<classElemType>boolLinkStack<ElemType>::Top(ElemType&e)const//操作結(jié)果：如棧非空,用e返回棧頂元素,返回true,否則// 返回false{ if(Empty()) { //?？? returnfalse; //失敗 } else { //棧非空,操作成功 e=top->data; //用e返回棧頂元素 returntrue; //成功 }}template<classElemType>voidLinkStack<ElemType>::Traverse(void(*visit)( constElemType&))const//操作結(jié)果：從棧底到棧頂依次對(duì)棧的每個(gè)元素調(diào)用函// 數(shù)(*visit){ Node<ElemType>*temPtr; //臨時(shí)指針變量 LinkStack<ElemType>temS; //臨時(shí)棧,temS中元素

//順序與當(dāng)前棧元素順序相反 for(temPtr=top;temPtr!=NULL; temPtr=temPtr->next) { //用temPtr依次指向當(dāng)前棧的每個(gè)元素 temS.Push(temPtr->data);

//對(duì)當(dāng)前棧的每個(gè)元素入棧到temS中 }

for(temPtr=temS.top;temPtr!=NULL; temPtr=temPtr->next) { //用temPtr從依次指向棧temS的每個(gè)元素 (*visit)(temPtr->data);

//對(duì)棧temS的每個(gè)元素調(diào)用函數(shù)(*visit) }}3.2隊(duì)列一、隊(duì)列(Queue)的基本概念1.隊(duì)列的初步認(rèn)識(shí)定義隊(duì)列是只允許在一端刪除，在另一端插入的線性表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)a1

a2

a3

anfrontrear

（1）intLength()const

初始條件：隊(duì)列已存在。

操作結(jié)果：返回隊(duì)列長(zhǎng)度

（2）boolEmpty()const

初始條件：隊(duì)列已存在。

操作結(jié)果：如隊(duì)列為空，則返回true，否則返回false

（3）voidClear()

初始條件：隊(duì)列已存在。

操作結(jié)果：清空隊(duì)列2.隊(duì)列的基本操作（4）voidTraverse(void(*visit)(

constElemType&))const

初始條件：隊(duì)列已存在。

操作結(jié)果：依次對(duì)隊(duì)列的每個(gè)元素調(diào)用函數(shù)(*visit)

（5）boolOutQueue(ElemType&e)

初始條件：隊(duì)列非空。

操作結(jié)果：刪除隊(duì)頭元素，并用e返回其值。

a1a2an……

隊(duì)頭隊(duì)尾（6）boolOutQueue()

初始條件：隊(duì)列非空。

操作結(jié)果：刪除隊(duì)頭元素。

（7）boolGetHead(ElemType&e)const

初始條件：隊(duì)列非空。

操作結(jié)果：用e返回隊(duì)頭元素。

a1a2an……隊(duì)頭隊(duì)尾（8）boolInQueue(constElemType&e)

初始條件：隊(duì)列已存在。

操作結(jié)果：插入元素e為新的隊(duì)尾。a1a2ane……隊(duì)頭隊(duì)尾二、鏈隊(duì)列1.鏈隊(duì)列的基本概念鏈?zhǔn)疥?duì)列在入隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。隊(duì)空條件為front==rear//鏈隊(duì)列類模板template<classElemType>classLinkQueue{protected://鏈隊(duì)列實(shí)現(xiàn)的數(shù)據(jù)成員:

Node<ElemType>*front,*rear;//隊(duì)頭隊(duì)尾指針

intcount; //元素個(gè)數(shù)public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明:

LinkQueue();

//無(wú)參數(shù)的構(gòu)造函數(shù)模板

virtual~LinkQueue();

//析構(gòu)函數(shù)模板2.鏈隊(duì)列的類模板

intLength()const;

//求隊(duì)列長(zhǎng)度

boolEmpty()const;

//判斷隊(duì)列是否為空

voidClear();

//將隊(duì)列清空

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

//遍歷隊(duì)列

boolOutQueue(ElemType&e); //出隊(duì)操作

boolOutQueue(); //出隊(duì)操作

boolGetHead(ElemType&e)const; //取隊(duì)頭操作

boolInQueue(constElemType&e); //入隊(duì)

LinkQueue(constLinkQueue<ElemType>&source); //復(fù)制構(gòu)造函數(shù)模板

LinkQueue<ElemType>&operator=(const LinkQueue<ElemType>&source);//重載賦值};三、循環(huán)隊(duì)列——隊(duì)列的

順序存儲(chǔ)結(jié)構(gòu)1.順序隊(duì)列的入隊(duì)和出隊(duì)frontrear空隊(duì)列frontrearA入隊(duì)AfrontrearB入隊(duì)ABfrontrearC,D入隊(duì)ABCDfrontrearA出隊(duì)BCDfrontrearB出隊(duì)CDfrontrearE,F,G入隊(duì)CDEFGCDEFGfrontrearH入隊(duì),溢出隊(duì)列的實(shí)際可用空間還沒(méi)有使用完，這種情況下再插入一個(gè)新元素產(chǎn)生的溢出稱主“假溢出”2.順序隊(duì)列的入隊(duì)和出隊(duì)原則

入隊(duì)時(shí)將新元素按

rear指示位置加入再將隊(duì)尾rear自加1:rear=rear+1。

出隊(duì)時(shí)將下標(biāo)為

front的元素取出,再將隊(duì)頭front自加1:front=front+1。

隊(duì)滿時(shí)再入隊(duì)將溢出出錯(cuò)；隊(duì)空時(shí)再出隊(duì)將隊(duì)空處理。解決假溢出方法：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)(環(huán)形)隊(duì)列。

隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭front、隊(duì)尾rear自加1時(shí)從maxSize-1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭front自加1:front=(front+1)%maxSize;隊(duì)尾rear自加1:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：count==0;隊(duì)滿條件：count==maxSize。 3.循環(huán)隊(duì)列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A入隊(duì)B,C入隊(duì)0123456701234567A出隊(duì)B出隊(duì)01234567D,E,F,G,H,I入隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHI4.循環(huán)隊(duì)列入隊(duì)和出隊(duì)示意圖//循環(huán)隊(duì)列類模板template<classElemType>classCircQueue{protected:

ElemType*elem; //元素存儲(chǔ)空間 intfront,rear; //隊(duì)頭隊(duì)尾

intmaxSize; //隊(duì)列最大元素個(gè)數(shù)

intcount; //元素個(gè)數(shù)public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明:

CircQueue(intsize=DEFAULT_SIZE);

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

virtual~CircQueue(); //析構(gòu)函數(shù)模板5.循環(huán)隊(duì)列的類模板

intLength()const; //求隊(duì)列長(zhǎng)度

boolEmpty()const; //判斷隊(duì)列是否為空

voidClear(); //將隊(duì)列清空

voidTraverse(void(*visit)(constElemType&))const; //遍歷隊(duì)列

boolOutQueue(ElemType&e); //出隊(duì)操作

boolOutQueue(); //出隊(duì)操作

boolGetHead(ElemType&e)const; //取隊(duì)頭操作

boolInQueue(constElemType&e); //入隊(duì)

CircQueue(constCircQueue<ElemType>&source); //復(fù)制構(gòu)造函數(shù)模板

CircQueue<ElemType>&operator=(const CircQueue<ElemType>&source); //重載賦值運(yùn)算符};template<classElemType>voidCircQueue<ElemType>::Traverse(void(*visit)( constElemType&))const//操作結(jié)果：依次對(duì)隊(duì)列的每個(gè)元素調(diào)用函數(shù)(*visit){ for(inttemPos=front;temPos!=rear; temPos=(temPos+1)%maxSize) { //對(duì)隊(duì)列的每個(gè)元素調(diào)用函數(shù)(*visit) (*visit)(elems[temPos]); }}6.部分成員函數(shù)模板的實(shí)現(xiàn)template<classElemType>boolCircQueue<ElemType>::OutQueue(ElemType&e)//操作結(jié)果：如果隊(duì)列非空，那么刪除隊(duì)頭元素，并用e// 返回其值，返回true,否則返回false{ if(!Empty()) { //隊(duì)列非空 e=elems[front]; //用e返回隊(duì)頭元素 front=(front+1)%maxSize; //front指向下一元素 count--; //出隊(duì)成功后元素個(gè)數(shù)自減1 returntrue; //成功 } else { //隊(duì)列為空 returnfalse; //失敗 }}template<classElemType>boolCircQueue<ElemType>::InQueue( constElemType&e)//操作結(jié)果：如果隊(duì)列已滿，返回false否則插入元素e為// 新的隊(duì)尾，返回true{ if(count==maxSize) { //隊(duì)列已滿 returnfalse; //失敗 } else { //隊(duì)列未滿，入隊(duì)成功 elems[rear]=e; //插入e為新隊(duì)尾 rear=(rear+1)%maxSize;//rear指向新隊(duì)尾 count++; //入隊(duì)成功后元素個(gè)數(shù)加1 returntrue; //成功 }}*3.3實(shí)例研究——表達(dá)式求值一、表達(dá)式基礎(chǔ)一個(gè)表達(dá)式由操作數(shù)(亦稱運(yùn)算對(duì)象)、操作符

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

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

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

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

表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算。算符優(yōu)先法就是根據(jù)上面的運(yùn)算符優(yōu)先關(guān)系來(lái)實(shí)現(xiàn)對(duì)表達(dá)式進(jìn)行編譯執(zhí)行任何表達(dá)式都可看成由操作數(shù)（operand）、操作符（operator）和界限符（delimiter）組成為簡(jiǎn)單起見(jiàn)，只討論算要四則運(yùn)算符（“+”、“-”、“*”、“/”），操作數(shù)為常數(shù)，界限符為左右圓括和等號(hào)（“（”，“）”，“=”）；三、算符優(yōu)先法對(duì)于任意兩個(gè)操作符theta1和theta2的優(yōu)先關(guān)系如下：theta1<theta2：theta1優(yōu)先級(jí)低于theta2。theta1=theta2：theta1優(yōu)先級(jí)等于theta2。theta1>theta2：theta1優(yōu)先級(jí)高于theta2。theta1etheta2：theta1與theta2不允許相繼出現(xiàn)。四、操作符的優(yōu)先級(jí)操作符優(yōu)先級(jí)相等的情況只出現(xiàn)在括號(hào)配對(duì)或左右操作符都是'='的情形。五、中綴算術(shù)表達(dá)式求值算法使用兩個(gè)棧，操作符棧optr(operator)，操作數(shù)棧opnd(operand)，對(duì)中綴表達(dá)式求值的一般規(guī)則：在optr棧中壓入一個(gè)'='

。從輸入流獲取一字符ch。取出optr的棧頂optrTop。當(dāng)optrTop!='='或ch!='='

時(shí),循環(huán)執(zhí)行以下工作,否則結(jié)束算法。此時(shí)在opnd棧的棧頂?shù)玫竭\(yùn)算結(jié)果。

while(optrTop!='='

||ch!='

='

){

①若ch不是操作符，則將字符放回輸入流(cin.putback)，讀操作數(shù)operand并進(jìn)opnd棧，并讀入下一字符送入ch；②若ch是操作符，將比較ch的優(yōu)先級(jí)和optrTop的優(yōu)先級(jí)：