《數(shù)據(jù)結(jié)構(gòu)》課件1第3章 棧和隊(duì)列

第3章棧和隊(duì)列棧

棧的定義順序棧的表示和實(shí)現(xiàn)

鏈棧的表示和實(shí)現(xiàn)隊(duì)列隊(duì)列的定義

循環(huán)隊(duì)列

鏈隊(duì)列3.1棧1.棧的定義2棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的插入操作稱為入棧，棧的刪除操作稱為出棧。不含任何數(shù)據(jù)元素的棧稱為空棧。設(shè)有棧S=(a1，a2，a3,，…，an)，則一般稱a1為棧底元素，an為棧頂元素。入棧：按a1，a2，a3,，…，an的順序出棧：按an，an-1，…，a2，a1的順序棧稱為后進(jìn)先出的線性表（LIFO：LastInFirstOut）a2a1an...棧底棧頂入棧出棧棧的基本操作操作結(jié)果intLength()返回棧元素個(gè)數(shù)boolEmpty()如棧為空，則返回true，否則返回falsevoidClear()清空棧boolPush(Te)插入元素e為新的棧頂元素boolTop(T&e)用e返回棧頂元素boolPop(T&e)刪除棧頂元素，并用e返回棧頂元素3.1棧2.順序棧的表示和實(shí)現(xiàn)3順序棧是指利用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。順序?？梢杂靡痪S數(shù)組來實(shí)現(xiàn)。通常把數(shù)組中下標(biāo)為0的一端作為棧底，同時(shí)附設(shè)變量top指示棧頂元素在數(shù)組中的位置。設(shè)存儲棧的數(shù)組長度為maxSize，則棧空時(shí)棧頂位置top=-1，棧滿時(shí)棧頂位置top=maxSize-1。入棧時(shí)，棧頂位置top加1；出棧時(shí)，棧頂位置top-1。3.1棧2.順序棧的表示和實(shí)現(xiàn)4類模板定義template<typenameT>classSqStack{private: inttop; //棧頂元素在數(shù)組中的下標(biāo) intmaxSize; //?？捎玫淖畲笕萘?T*elem; //存儲空間的基地址public: SqStack(intsize=DEFAULT_SIZE); //構(gòu)造函數(shù)SqStack(SqStack<T>&st); //復(fù)制構(gòu)造函數(shù) ~SqStack(); //析構(gòu)函數(shù) intLength(); //返回棧中元素個(gè)數(shù)boolEmpty(); //判斷棧是否為空voidClear(); //清空棧 boolPush(Te); //入棧 boolPop(T&e); //出棧 boolGetTop(T&e); //返回棧頂元素};3.1棧2.順序棧的表示和實(shí)現(xiàn)5基本操作//返回棧中元素個(gè)數(shù)template<typenameT>intSqStack<T>::Length(){ returntop+1;}//判斷棧是否為空template<typenameT>boolSqStack<T>::Empty(){ returntop==-1;}//清空順序表template<typenameT>voidSqStack<T>::Clear(){ top=-1;}//入棧template<typenameT>boolSqStack<T>::Push(Te){ if(top==maxSize-1) returnfalse; elem[++top]=e; returntrue;}//返回棧頂元素template<typenameT>boolSqStack<T>::GetTop(T&e){ if(top==-1) returnfalse; e=elem[top]; returntrue;}//出棧template<typenameT>boolSqStack<T>::Pop(T&e){ if(top==-1) returnfalse; e=elem[top--]; returntrue;}3.1棧3.鏈棧的表示和實(shí)現(xiàn)6鏈棧是指采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧，通常用單鏈表來表示。由于棧的插入和刪除操作只能在棧頂執(zhí)行，因此以單鏈表的頭部作為棧頂是最方便的，而且沒有必要像單鏈表那樣為了運(yùn)算方便附加一個(gè)頭結(jié)點(diǎn)。鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同template<typenameT>structStNode{ Tdata; StNode<T>*next;};3.1棧3.鏈棧的表示和實(shí)現(xiàn)7類模板定義template<typenameT>classLinkStack{private: StNode<T>*top;

//棧頂指針public: LinkStack(); //構(gòu)造函數(shù) LinkStack(LinkStack<T>&lst); //復(fù)制構(gòu)造函數(shù) ~LinkStack(); //析構(gòu)函數(shù) intLength(); //返回棧中元素個(gè)數(shù)boolEmpty(); //判斷棧是否為空 voidClear(); //清空棧boolPush(Te); //入棧 boolPop(T&e); //出棧 boolGetTop(T&e); //返回棧頂元素};3.1棧3.鏈棧的表示和實(shí)現(xiàn)8基本操作//返回棧中元素個(gè)數(shù)template<typenameT>intLinkStack<T>::Length(){ intlen=0; StNode<T>*p=top; while(p!=NULL) { len++; p=p->next; } returnlen;}//判斷棧是否為空template<typenameT>boolLinkStack<T>::Empty(){ returntop==NULL;}//清空順序表template<typenameT>voidLinkStack<T>::Clear(){ StNode<T>*p; while(top!=NULL) { p=top; top=p->next; deletep; }}//返回棧頂元素template<typenameT>boolLinkStack<T>::GetTop(T&e){ if(top==NULL) returnfalse; e=top->data; returntrue;}3.1棧3.鏈棧的表示和實(shí)現(xiàn)9入棧template<typenameT>boolLinkStack<T>::Push(Te){ StNode<T>*p=newStNode<T>; //生成新結(jié)點(diǎn)

if(p==NULL) //動態(tài)內(nèi)存耗盡

returnfalse; p->data=e; //將新結(jié)點(diǎn)數(shù)據(jù)域置為e p->next=top; //將新結(jié)點(diǎn)插入棧頂

top=p; //修改棧頂指針

returntrue;}3.1棧3.鏈棧的表示和實(shí)現(xiàn)10出棧template<typenameT>boolLinkStack<T>::Pop(T&e){ if(top==NULL) //?？?/p>

returnfalse; StNode<T>*old_top=top; e=old_top->data; //用e保存棧頂元素的值

top=old_top->next; //修改棧頂指針

deleteold_top; //釋放原棧頂元素的空間

returntrue;}3.1棧4.棧的應(yīng)用——進(jìn)制轉(zhuǎn)換問題11【問題分析】將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)的方法很多，其中一個(gè)常用的算法是“除2取余法”。上述計(jì)算過程是從低位到高位順序產(chǎn)生二進(jìn)制數(shù)的各個(gè)數(shù)位，而輸出過程應(yīng)從高位到低位進(jìn)行，恰好和計(jì)算過程相反，因此可以使用棧來解決這個(gè)問題。在計(jì)算過程中依次將得到的余數(shù)壓入棧中，計(jì)算完畢后，將棧中的余數(shù)依次出棧輸出，輸出結(jié)果就是轉(zhuǎn)換后的二進(jìn)制數(shù)?！舅惴ú襟E】(1)當(dāng)n≠0時(shí)重復(fù)執(zhí)行以下操作：①計(jì)算n除以2的余數(shù)并將其壓入棧中；②用n/2代替n。(2)重復(fù)執(zhí)行以下操作直到棧為空：彈出棧頂元素，并輸出被彈出元素的值。3.1棧4.棧的應(yīng)用——括號匹配問題12【問題分析】給定一個(gè)算數(shù)表達(dá)式，目測怎么判斷括號是否匹配呢？可以從左向右看這個(gè)表達(dá)式中的括號，看到一個(gè)“(”就記住它，如果下一個(gè)括號是“)”，則劃掉這兩個(gè)括號，如果下一個(gè)括號還是“(”，則暫時(shí)不管前一個(gè)“(”，先把它放在那里，等后面的“(”處理完再來處理它，這正好符合棧的后進(jìn)先出特性，因此可以使用棧來解決這個(gè)問題。從左向右依次掃描表達(dá)式字符串中的各字符，若讀入的是“(”，則進(jìn)棧；若讀入的是“)”，且棧不為空則出棧，如果棧空則說明沒有與之匹配的左括號，匹配失敗。當(dāng)表達(dá)式掃描結(jié)束時(shí)，若棧為空則匹配成功，否則，說明沒有與棧中的“(”相匹配的“)”，匹配失敗?！舅惴ú襟E】(1)初始化一個(gè)空棧。(2)掃描表達(dá)式，依次讀入字符，直到表達(dá)式掃描完畢。①如果讀入的字符是’(‘，則將其壓入棧；②如果讀入的字符是’)‘，且棧非空，則彈出棧頂元素；如果棧為空，則括號不匹配，返回false。(3)如果棧為空，則左右括號匹配，返回true；否則括號不匹配，返回false。3.2隊(duì)列1.隊(duì)列的定義13隊(duì)列的基本操作隊(duì)列是限定只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。允許刪除（出隊(duì)）的一端叫做隊(duì)頭允許插入（入隊(duì)）的一端叫做隊(duì)尾入隊(duì)和出隊(duì)的順序相同先進(jìn)先出（FIFO）a1a2a3

anfrontrear入隊(duì)出隊(duì)操作結(jié)果intLength()返回隊(duì)列長度boolEmpty()如隊(duì)列為空，則返回true，否則返回falsevoidClear()清空隊(duì)列boolOutQueue(T&e)刪除隊(duì)頭元素，并用e返回其值boolGetHead(T&e)用e返回隊(duì)頭元素boolInQueue(Te)插入元素e為新的隊(duì)尾3.2隊(duì)列2.循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)14隊(duì)列的順序表示就是用一組地址連續(xù)的存儲單元依次存放從隊(duì)頭到隊(duì)尾的元素?？梢杂脭?shù)組elem[maxSize]作為隊(duì)列的順序存儲空間，maxSize為隊(duì)列的容量，隊(duì)頭元素放在下標(biāo)為0的一端由于隊(duì)列的隊(duì)頭和隊(duì)尾都是活動的，因此需要附設(shè)兩個(gè)整型變量front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。初始化創(chuàng)建空隊(duì)列時(shí)，令front=rear=0，插入新元素時(shí)，rear加1；刪除元素時(shí)，front加1。因此，在非空隊(duì)列中，front始終指向隊(duì)頭元素，而rear始終指向隊(duì)尾元素的下一個(gè)位置。假設(shè)當(dāng)前隊(duì)列分配的最大空間為6，則當(dāng)隊(duì)列處于圖3-10（d）所示的狀態(tài)時(shí)不可再繼續(xù)插入新的隊(duì)尾元素，否則會出現(xiàn)溢出現(xiàn)象，即因數(shù)組越界而導(dǎo)致的非法操作錯(cuò)誤。事實(shí)上，此時(shí)隊(duì)列的實(shí)際可用空間并未占滿，所以這種現(xiàn)象稱為“假溢出”。這是由“隊(duì)尾入隊(duì)，隊(duì)頭出隊(duì)”這種受限制的操作造成的。3.2隊(duì)列2.循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)15解決假溢出的方法是將隊(duì)列從邏輯上看成一個(gè)環(huán)——循環(huán)隊(duì)列循環(huán)隊(duì)列的首尾相接，當(dāng)隊(duì)頭front和隊(duì)尾rear進(jìn)入到maxSize-1時(shí)，再進(jìn)一個(gè)位置就自動地移動到0，可用取模運(yùn)算來實(shí)現(xiàn)。隊(duì)頭進(jìn)1：front=(front+1)%maxSize隊(duì)尾進(jìn)1：rear=(rear+1)%maxSize對于循環(huán)隊(duì)列不能以front和rear的值是否相等來判斷隊(duì)列空間是空還是滿。在這種情況下，如何區(qū)分隊(duì)滿還是隊(duì)空呢？少用一個(gè)元素空間隊(duì)列空間大小為n時(shí)，有n-1個(gè)元素就認(rèn)為是隊(duì)滿。隊(duì)空的條件：front==rear隊(duì)滿的條件：(rear+1)%maxSize==front另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿3.2隊(duì)列2.循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)16類模板定義template<typenameT>classSqQueue{pravite: intfront,rear; //指示隊(duì)頭和隊(duì)尾的位置

intmaxSize; //隊(duì)列的最大容量

T*elem; //存儲空間的基地址

public: SqQueue(intsize=MAXSIZE); //構(gòu)造函數(shù)

SqQueue(SqQueue<T>&sq); //復(fù)制構(gòu)造函數(shù)

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

intLength(); //返回隊(duì)列的長度

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

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

boolInQueue(Te); //入隊(duì)

boolOutQueue(T&e); //出隊(duì)

boolGetHead(T&e); //返回隊(duì)頭元素};3.2隊(duì)列2.循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)17基本操作//返回隊(duì)列長度template<typenameT>intSqQueue<T>::Length(){ return(rear-front+maxSize)%maxSize;}//判斷隊(duì)列是否為空template<typenameT>boolSqQueue<T>::Empty(){ returnfront==rear;}//入隊(duì)template<typenameT>boolSqQueue<T>::InQueue(Te){ if((rear+1)%maxSize==front) returnfalse; elem[rear]=e; rear=(rear+1)%maxSize; returntrue;}//清空隊(duì)列template<typenameT>voidSqQueue<T>::Clear(){ rear=front=0;}//出隊(duì)template<typenameT>boolSqQueue<T>::OutQueue(T&e){ if(rear==front) returnfalse; e=elem[front]; front=(front+1)%maxSize; returntrue;}//返回隊(duì)頭元素template<typenameT>boolSqQueue<T>::GetHead(T&e){ if(rear==front) returnfalse; e=elem[front]; returntrue;}3.2隊(duì)列3.鏈隊(duì)——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)18隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊(duì)，通常用單鏈表表示。結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。隊(duì)頭隊(duì)尾a1a2an

∧…頭指針front尾指針rear頭結(jié)點(diǎn)非空鏈隊(duì)列：空鏈隊(duì)列：∧頭指針front尾指針rear頭結(jié)點(diǎn)3.2隊(duì)列3.鏈隊(duì)——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)19類模板定義template<typenameT>classLinkQueue{private: QuNode<T>*front,*rear; public: LinkQueue(); //構(gòu)造函數(shù)

LinkQueue(LinkQueue<T>&lq);

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

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

intLength(); //返回隊(duì)列長度

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

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

boolInQueue(Te); //入隊(duì)

boolOutQueue(T&e); //出隊(duì)

boolGetHead(T&e); //獲取隊(duì)頭元素};3.2隊(duì)列3.鏈隊(duì)——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)20基本操作//返回隊(duì)列長度template<typenameT>intLinkQueue<T>::Length(){ intlen=0; QuNode<T>*p=front->next; while(p!=NULL) { len++; p=p->next; } returnlen;}//判斷隊(duì)列是否為空template<typenameT>boolLinkQueue<T>::Empty(){ returnfront==rear;}//清空隊(duì)列template<typenameT>voidLinkQueue<T>::Clear(){ QuNode<T>*p=front->next; while(p!=NULL) //刪除所有數(shù)據(jù)結(jié)點(diǎn)

{ front->next=p->next; deletep; p=front->next; } rear=front; //rear指向頭結(jié)點(diǎn)}//返回隊(duì)頭元素template<typenameT>boolLinkQueue<T>::GetHead(T&e){ if(front==rear) returnfalse; e=front->next->data; returntrue;}3.2隊(duì)列3.鏈隊(duì)——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)21入隊(duì)template<typenameT>boolLinkQueue<T>::InQueue(Te){ QuNode<T>*p=newQuNode<T>; //生成新結(jié)點(diǎn)

if(p==NULL) //動態(tài)內(nèi)存耗盡

returnfalse; p->data=e; p->next=NULL; rear->next=p; //新結(jié)點(diǎn)鏈入隊(duì)尾

rear=p; //重新設(shè)置隊(duì)尾指針

returntrue;}3.2隊(duì)列3.鏈隊(duì)——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)22出隊(duì)template<typenameT>boolLi