棧和隊列基礎(chǔ)知識

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

2、p（st）：刪除（亦稱彈出）棧st的頂部元素。l 取棧頂 top（st）：取棧st的頂部元素。1.棧相關(guān)知識 棧的兩種實(shí)現(xiàn)方式棧的兩種實(shí)現(xiàn)方式順序棧和鏈棧 順序棧順序棧利用一組地址連續(xù)的存儲單元依次存放自棧頂?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型簡單變量 ,指向棧頂元素在棧中的位置(序號) 6 5 4 3 2 1 0-11.棧相關(guān)知識 順序棧順序棧約定:1、?？諘r，t=-12、棧滿時，t=MAXNUM-13、棧頂元素：St4、若t=-1時，執(zhí)行出棧操作,產(chǎn)生“下溢”5、若t=MAXNUM-1時，執(zhí)行入棧,產(chǎn)生“上溢”ABCD入棧和出棧1.棧相關(guān)知識 鏈棧鏈棧棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧。由于只能在鏈表頭部進(jìn)行操作，故鏈棧沒有必要像單鏈表那樣需附加頭結(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 .隊列相關(guān)知識2. 隊列相關(guān)知識l 隊列：只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除l 隊頭：允許刪除的一端l 隊尾：允許插入的一端出隊入隊隊頭隊尾a1 a2 an . 隊列是先進(jìn)先

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

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

7、2. 隊列相關(guān)知識 鏈隊列鏈隊列隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。 顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表上的最后一個結(jié)點(diǎn)。于是，一個鏈隊列由一個頭指針和一個尾指針唯一地確定。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)方式，分別為順序棧和鏈棧。隊列是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種先進(jìn)先出（FIFO)的數(shù)據(jù)結(jié)構(gòu)，允許刪除的一端稱為隊頭，允許插入的一端稱為隊尾。隊列有兩種實(shí)現(xiàn)方式，