棧和隊(duì)列基礎(chǔ)知識(shí)

1、棧和隊(duì)列基礎(chǔ)知識(shí)C程 序 設(shè) 計(jì)CONTENTS 棧相關(guān)知識(shí) 隊(duì)列相關(guān)知識(shí) 總結(jié)棧相關(guān)知識(shí)1.棧相關(guān)知識(shí)l 棧： 限制僅在一端進(jìn)行插入和刪除運(yùn)算的線性表?xiàng)ｍ敆ｍ敆５讞５兹霔Ｈ霔３鰲３鰲 棧頂：進(jìn)行插入、刪除的一端l 棧底：除棧頂外的另一端.a2a1an棧是后進(jìn)先出表（ LIFO ） 棧的概念棧的概念 棧的基本操作棧的基本操作1.棧相關(guān)知識(shí)l 置空棧 createEmptyStack(void)：空棧；l 判?？?isEmptytack（st）：這是一個(gè)布爾函數(shù)。若st為空棧，則函數(shù)值為“真”, 否則為“假”。l 入棧 push（st，x）：在st的頂部插入(亦稱壓入）元素 x。l 出棧 po

2、p（st）：刪除（亦稱彈出）棧st的頂部元素。l 取棧頂 top（st）：取棧st的頂部元素。1.棧相關(guān)知識(shí) 棧的兩種實(shí)現(xiàn)方式棧的兩種實(shí)現(xiàn)方式順序棧和鏈棧 順序棧順序棧利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧頂?shù)綏５椎臄?shù)據(jù)元素。#define MAXNUM 100 /* 棧中能達(dá)到的最大容量棧中能達(dá)到的最大容量*/ typedef int DataType; /* 定義棧元素的數(shù)據(jù)類型定義棧元素的數(shù)據(jù)類型* /struct SeqStack /* 順序棧類型定義順序棧類型定義 */DataType sMAXNUM;int t; /*棧頂棧頂*/；typedef struct SeqStack,

3、*PSeqStack;PSeqStack pastack; /*指向順序棧的指針變量指向順序棧的指針變量*/t是 int型簡(jiǎn)單變量 ,指向棧頂元素在棧中的位置(序號(hào)) 6 5 4 3 2 1 0-11.棧相關(guān)知識(shí) 順序棧順序棧約定:1、?？諘r(shí)，t=-12、棧滿時(shí)，t=MAXNUM-13、棧頂元素：St4、若t=-1時(shí)，執(zhí)行出棧操作,產(chǎn)生“下溢”5、若t=MAXNUM-1時(shí)，執(zhí)行入棧,產(chǎn)生“上溢”ABCD入棧和出棧1.棧相關(guān)知識(shí) 鏈棧鏈棧棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。由于只能在鏈表頭部進(jìn)行操作，故鏈棧沒(méi)有必要像單鏈表那樣需附加頭結(jié)點(diǎn)。棧頂指針top就是鏈表的頭指針head。 typedef int

4、DataType; typedef struct Node /* 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) */ DataType info; pNode link; *pNode;struct LinkStack/* 鏈接棧類型定義鏈接棧類型定義 */pNode top;/* 指向棧頂結(jié)點(diǎn)指向棧頂結(jié)點(diǎn) */;typedef struct LinkStack *PLinkStack;棧的鏈接表示棧的鏈接表示 top info link .隊(duì)列相關(guān)知識(shí)2. 隊(duì)列相關(guān)知識(shí)l 隊(duì)列：只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除l 隊(duì)頭：允許刪除的一端l 隊(duì)尾：允許插入的一端出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾a1 a2 an . 隊(duì)列是先進(jìn)先

5、出表（FIFO）2. 隊(duì)列相關(guān)知識(shí) 隊(duì)列的基本操作隊(duì)列的基本操作l 創(chuàng)建一個(gè)空隊(duì)列 Queue createEmptyQueue ( void ) l 判隊(duì)列是否為空隊(duì)列 int isEmptyQueue ( Queue qu ) l 往隊(duì)列中插入一個(gè)元素 void enQueue ( Queue qu, DataType x ) l 從隊(duì)列中刪除一個(gè)元素 void deQueue ( Queue qu ) l 求隊(duì)列頭部元素的值 DataType frontQueue ( Queue qu ) 2. 隊(duì)列相關(guān)知識(shí) 隊(duì)列的兩種實(shí)現(xiàn)方式隊(duì)列的兩種實(shí)現(xiàn)方式順序隊(duì)列和鏈隊(duì)列 順序隊(duì)列順序隊(duì)列隊(duì)列的順

6、序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序隊(duì)列 由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置均是變化的，因而要設(shè)置兩個(gè)指針，分別指示當(dāng)前隊(duì)頭元素和隊(duì)尾元素在向量空間中的位置。#define MAXNUM 100struct SeqQueue datatype qMAXNUM; int f, r;typedef struct SeqQueue *PSeqQueue;PSeqQueue sq;2. 隊(duì)列相關(guān)知識(shí) 順序隊(duì)列的入隊(duì)和出隊(duì)操作順序隊(duì)列的入隊(duì)和出隊(duì)操作隊(duì)列空： sq-f=0; sq-r=0; 入隊(duì)： sq-qsq-r=x; sq-r+; 出隊(duì)： sq-f+; 76543210frxryrf隊(duì)列長(zhǎng)度:（sq-r) - (sq-f)

7、2. 隊(duì)列相關(guān)知識(shí) 鏈隊(duì)列鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。 顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個(gè)尾指針，指向鏈表上的最后一個(gè)結(jié)點(diǎn)。于是，一個(gè)鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一地確定。typedef struct Node DataType info; pNodelink; *pNode;struct LinkQueue PNodef; PNoder;typedef struct LinkQueue, *PLinkQueue; k0 k1 k2 kn-1.ff總結(jié)3.總結(jié)棧是限制僅在一端進(jìn)行插入和刪除運(yùn)算的線性表，它是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。進(jìn)行插入、刪除的一端稱為棧頂。棧有兩種實(shí)現(xiàn)方式，分別為順序棧和鏈棧。隊(duì)列是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種先進(jìn)先出（FIFO)的數(shù)據(jù)結(jié)構(gòu)，允許刪除的一端稱為隊(duì)頭，允許插入的一端稱為隊(duì)尾。隊(duì)列有兩種實(shí)現(xiàn)方式，