高中二年級(jí)下學(xué)期信息科技《用棧組織后進(jìn)先出數(shù)據(jù)》教學(xué)課件

選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》3.4用棧組織后進(jìn)先出數(shù)據(jù)|一、棧Stack|棧Stack|隊(duì)列對(duì)應(yīng)了生活中的排隊(duì)現(xiàn)象但還有另一種現(xiàn)象，如對(duì)一疊碗的取放：每次把洗凈的碗放好時(shí)總是放在這疊碗的最上面，而每次取用的時(shí)候也總是取最上面的。在這種現(xiàn)象中，事物的進(jìn)出順序都有共同的特征，那就是后進(jìn)先出。|棧(Stack)是限制只能在一端進(jìn)行插入和刪除的特殊線性表。棧中能進(jìn)行插入和刪除的一端稱為棧頂(Top)，而另一固定端稱為棧底(Bottom)。把一個(gè)數(shù)據(jù)元素放入棧中的操作叫作進(jìn)?；驂簵?Push)，從棧中取出一個(gè)數(shù)據(jù)元素的操作稱為出?；驈棾?Pop)。棧中沒(méi)有元素時(shí)，稱為空棧。棧的形式在日常生活中經(jīng)常出現(xiàn)，如一疊書、一疊盤子，如果規(guī)定取書、取盤子或放入書、放入盤子都只能在頂部進(jìn)行，則它就是一個(gè)棧。棧的特性：后放入棧中的數(shù)據(jù)元素首先取出。故棧又被稱為后進(jìn)先出(LIFO:LastInFirstOut)線性表。棧Stack建立數(shù)據(jù)模型|棧{

棧元素（一定數(shù)量的購(gòu)物車編號(hào)）；

棧頂（即將出棧的購(gòu)物車的位置）；

棧底（即堆在最底的購(gòu)物車的位置）；}棧的基本操作；二、棧的基本操作Basicoperationofstack|棧的基本操作|棧的常用基本操作有以下幾種：（1）初始化棧：構(gòu)造一個(gè)空棧，初始化棧頂標(biāo)志。（2）元素入棧：若棧非滿，棧頂標(biāo)志上移一位，插入一個(gè)元素到棧頂標(biāo)志指向的位置，該元素成為新的棧頂元素。（3）元素出棧：刪除棧頂標(biāo)志指向的棧頂元素，棧頂標(biāo)志下移一位，若此時(shí)棧非空，則棧頂標(biāo)志指向的元素成為新的棧頂元素。（4）棧空判斷：判斷棧是否為空。（5）棧滿判斷：判斷棧是否為滿。（6）棧的長(zhǎng)度：求棧的元素個(gè)數(shù)。棧的基本操作|352棧頂一種“后進(jìn)先出”的結(jié)構(gòu)加入一個(gè)數(shù)4取出棧頂元素再取出棧頂元素6入棧：top++;a[top]=x;出棧：x=a[top];top--;三、順序棧的實(shí)現(xiàn)Implementationofsequentialstack|順序棧的實(shí)現(xiàn)棧的存儲(chǔ)也可采用順序存儲(chǔ)結(jié)構(gòu)的方法來(lái)實(shí)現(xiàn)，采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)置指針top來(lái)動(dòng)態(tài)地指示棧頂元素的當(dāng)前位置。順序棧的實(shí)現(xiàn)|

初始化棧voidInitStack(Stack&st){q.top=-1;//把棧頂指針置為-1}順序隊(duì)列的操作代碼|

將元素x進(jìn)棧，元素進(jìn)棧成功返回true，否則返回false。入棧操作boolPushStack(Stack&st,stringx){if(st.top==maxsize-1)returnfalse;//棧滿不能插入元素，返回falseelse{ st.top++; st.item[st.top]=x; returntrue;//成功將元素入棧，返回true }}順序隊(duì)列的操作代碼|

將st的棧頂元素出棧，出棧元素存放在x中，出棧成功返回true，否則返回false。出棧操作boolPopStack(Stack&st,stringx){if(st.top==-1)returnfalse;//?？詹荒艹鰲?，返回falseelse{x=st.item[st.top];st.top--;returntrue;//成功將元素出棧，返回true }}順序隊(duì)列的操作代碼|

若棧st為空棧，則返回true，否則返回false。?？张袛郻oolEmptyStack(Stack&st){if(st.top==-1)returntrue; elsereturnfalse; }順序隊(duì)列的操作代碼|

若棧st為滿棧，則返回true，否則返回false。棧滿判斷boolFullStack(Stack&st){if(st.top==maxsize-1)returntrue; elsereturnfalse; }順序隊(duì)列的操作代碼|intStackLength(Stack&st){returnst.top+1; }

返回棧中當(dāng)前元素的個(gè)數(shù)。棧的長(zhǎng)度練習(xí)題目①若已知一個(gè)棧的入棧順序是1,2,3,…,n，其輸出序列為p1,p2,…,Pn，若p1是n，則pi是（）A.iB.n-1C.n-i+1D.不確定練習(xí)題目②設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e,f依次入棧S，出棧的序列為b,d,c,f,e,a，則棧S的容量至少應(yīng)該是（）A.6B.5C.4D.3E.2練習(xí)題目③設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過(guò)棧S,一個(gè)元素出棧后即