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

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

棧元素（一定數(shù)量的購物車編號）；

棧頂（即將出棧的購物車的位置）；

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

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

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

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

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

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

返回棧中當前元素的個數(shù)。棧的長度練習題目①若已知一個棧的入棧順序是1,2,3,…,n，其輸出序列為p1,p2,…,Pn，若p1是n，則pi是（）A.iB.n-1C.n-i+1D.不確定練習題目②設(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練習題目③設(shè)棧S和隊列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即