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

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

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

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

topbottom（1）intLength()const

初始條件：棧已存在。

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

（2）boolEmpty()const

初始條件：棧已存在。

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

（3）voidClear()

初始條件：棧已存在。

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

constElemType&))const

初始條件：棧已存在。

操作結(jié)果：從棧底到棧頂依次對棧的每個元素調(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存儲數(shù)組中存儲的棧的實際元素個數(shù)當(dāng)count=0時表示棧為空入棧操作時，如棧未滿，操作成功，count的值將加1出棧時，如棧不空，操作成功，并且count的值將減1//順序棧類模板template<classElemType>classSqStack{protected://順序棧的數(shù)據(jù)成員:

ElemType*elems; //元素存儲空間

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

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

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

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); //復(fù)制構(gòu)造函數(shù)模板

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

//重載賦值運算符};復(fù)制構(gòu)造函數(shù)模板template<classElemType>SqStack<ElemType>::SqStack( constSqStack<ElemType>&source)//操作結(jié)果：由棧source構(gòu)造新?！獜?fù)制構(gòu)造函數(shù)模板{ maxSize=source.maxSize; //最大元素個數(shù) elems=newElemType[maxSize];//分配存儲空間 count=source.count; //棧元素個數(shù) for(inttemPos=1;temPos<=Length();temPos++) { //從棧底到棧頂復(fù)制棧source的每個元素 elems[temPos-1]=source.elems[temPos-1]; }}template<classElemType>SqStack<ElemType>&SqStack<ElemType>::operator= (constSqStack<ElemType>&source)//操作結(jié)果：將棧source賦值給當(dāng)前?！剌d賦值運算符{ if(&source!=this) { maxSize=source.maxSize; //最大元素個數(shù) delete[]elems; //釋放存儲空間 elems=newElemType[maxSize];//分配存儲空間 count=source.count; //復(fù)制棧元素個數(shù) for(inttemPos=1;temPos<=Length();Pos++) { //從棧底到棧頂復(fù)制棧source的每個元素 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棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^鏈?zhǔn)綏Ｈ霔：统鰲２僮鞫挤浅：唵?，一般都不使用頭結(jié)點直接實現(xiàn)1.鏈?zhǔn)綏５幕靖拍?/鏈棧類模板template<classElemType>classLinkStack{protected://鏈棧實現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*top; //棧頂指針 intcount; //元素個數(shù)public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: LinkStack(); //無參數(shù)的構(gòu)造函數(shù)

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

intLength()const; //求棧長度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)造一個空棧表{ top=NULL; //構(gòu)造棧頂指針 count=0; //初始化元素個數(shù)}template<classElemType>LinkStack<ElemType>::~LinkStack()//操作結(jié)果：銷毀棧{ Clear();}3.部分成員函數(shù)模板的實現(xiàn)template<classElemType>boolLinkStack<ElemType>::Push( constElemType&e)//操作結(jié)果：將元素e追加到棧頂,如成功則返加true,否則如動// 態(tài)內(nèi)存已耗盡將返回false{ Node<ElemType>*newTop= newNode<ElemType>(e,top); if(newTop==NULL) { //動態(tài)內(nèi)存耗盡 returnfalse; //失敗 } else { //操作成功 top=newTop; count++; //入棧成功后元素個數(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--; //出棧成功后元素個數(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é)果：從棧底到棧頂依次對棧的每個元素調(diào)用函// 數(shù)(*visit){ Node<ElemType>*temPtr; //臨時指針變量 LinkStack<ElemType>temS; //臨時棧,temS中元素

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

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

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

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

a2

a3

anfrontrear

（1）intLength()const

初始條件：隊列已存在。

操作結(jié)果：返回隊列長度

（2）boolEmpty()const

初始條件：隊列已存在。

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

（3）voidClear()

初始條件：隊列已存在。

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

constElemType&))const

初始條件：隊列已存在。

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

（5）boolOutQueue(ElemType&e)

初始條件：隊列非空。

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

a1a2an……

隊頭隊尾（6）boolOutQueue()

初始條件：隊列非空。

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

（7）boolGetHead(ElemType&e)const

初始條件：隊列非空。

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

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

初始條件：隊列已存在。

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

Node<ElemType>*front,*rear;//隊頭隊尾指針

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

LinkQueue();

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

virtual~LinkQueue();

//析構(gòu)函數(shù)模板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); //復(fù)制構(gòu)造函數(shù)模板

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

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

入隊時將新元素按

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

出隊時將下標(biāo)為

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

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

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

ElemType*elem; //元素存儲空間 intfront,rear; //隊頭隊尾

intmaxSize; //隊列最大元素個數(shù)

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

CircQueue(intsize=DEFAULT_SIZE);

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

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

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); //復(fù)制構(gòu)造函數(shù)模板

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

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

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

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

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

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

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

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

while(optrTop!='='

||ch!='

='

){

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