資源描述：
《數(shù)據(jù)結(jié)構(gòu)棧和隊列課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容3.1棧（Stack）第三章棧和隊列3.2隊列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義3.1棧與同線性表相同，仍為一對一關(guān)系。用順序?；蜴湕４鎯桑皂樞驐８Ｒ娭荒茉跅ｍ?表尾)運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５牟煌煌??；静僮饔腥霔！⒊鰲?、讀棧頂元素值、建棧、或判斷棧滿、?？盏?。3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5
2、.實(shí)現(xiàn)方式2.邏輯結(jié)構(gòu)限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表（只能在棧頂操作）問：堆棧是什么？它與一般線性表有什么不同？3.1棧答：堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝壓入=PUSH（x)“出”＝彈出=POP(y)棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂top;表頭(
3、即a1端)稱為棧底base例如：棧s=(a1,a2,a3,……….,an-1,an)a1稱為棧底元素an稱為棧頂元素插入元素到棧頂（即表尾）的操作，稱為入棧。從棧頂（即表尾）刪除最后一個元素的操作，稱為出棧。教材P44對棧有更詳細(xì)定義：強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！順序棧示意圖sa1a2a3dataa4(棧底)(棧頂)99...3210topa1a2……an順序棧Sai……表和棧的操作區(qū)別——對線性表s=(a1,a2,….,an-1,an)表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=
4、ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預(yù)設(shè)棧頂指針top！低地址高地址v[i]a1a2aian……順序表V[n]……an+1入棧操作——例如用堆棧存放（A，B，C，D）（注意要遵循“后進(jìn)先出”原則）AACBABAtop核心語句：top=L;順序棧中的PUSH函數(shù)statusPush(ElemTypex){if(top>M){上溢}elsev[top++]=x;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD出棧
5、操作——例如從棧中取出‘B’（注意要遵循“后進(jìn)先出”原則）DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：Pop();Pop();Printf(Pop());順序棧中的POP函數(shù)statusPop(){if(top=L){下溢}else{y=v[--top];return(y);}}例1：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；12345的輸出可以實(shí)現(xiàn)，只
6、需壓入一個立即彈出一個即可。435612中到了12順序不能實(shí)現(xiàn)；135426可以實(shí)現(xiàn)。例2：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例3（嚴(yán)題集3.1）一個棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；
7、合計有5種可能性。補(bǔ)充1：若入棧動作使地址向高端增長，稱為“向上生成”的棧；若入棧動作使地址向低端增長，稱為“向下生成”的棧；對于向上生成的棧入?？谠E：堆棧指針top先壓后加（v[top++]=x）；出?？谠E：堆棧指針top先減后彈（y=v[--top])。3.1棧補(bǔ)充2：棧不存在的條件：base=NULL;棧為空的條件：base=top;棧滿的條件：top-base=stacksize;補(bǔ)充3：鏈棧鏈棧示意圖s(棧底)(棧頂)topa3a2a4a1^鏈棧的入棧函數(shù)、出棧函數(shù)（以頭指針為棧頂，在頭指針處插入或刪除
8、?。┕舱f明部分：typedefstructsnode{SElemTypedata;structsnode*link;}NODE;NODE*st,*p;intm=sizeof(NODE);Push(SElemTypex){p=(NODE*)malloc(m);if(!p){上溢}else{p->data=x;p->link=st;st=p;}}Statuspop(){if
