棧
特性后進(jìn)先出
只允許在一端進(jìn)行插入或刪除操作的線性表
每接觸一種新的數(shù)據(jù)結(jié)構(gòu)類型，都應(yīng)該分別從邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的運(yùn)算三方面入手
操作
initstack(&s)初始化一個(gè)空棧s
stackempty(s)判斷一個(gè)棧是否為空
push(&s,x)進(jìn)棧，未滿成為新棧頂
pop(&s,&x)出棧，非空彈出棧頂元素
gettop(s,&x)讀棧頂元素，用x返回棧頂元素
destroystack(&s)銷毀棧
順序存儲(chǔ)結(jié)構(gòu)
采用順序存儲(chǔ)的棧稱為順序棧
棧頂指針：S.top
初始設(shè)置S.top=-1
棧頂元素S.data[S.top]
?？諚l件：S.top==-1
棧滿條件：S.top==MaxSize-1
棧長(zhǎng)：S.top+1
注意：
top指向的是棧頂元素
進(jìn)棧操作為S.data[++S.top]=x
出棧操作為x=S.data[S.top–]
若棧頂指針初始化為S.top=0,top指向棧頂元素的下一位
入棧操作為S.data[S.top++]=x
出棧操作為x=S.data[–S.top]
共享?xiàng)?/strong>
棧滿 ：top1-top0=1
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
稱為鏈棧
便于多個(gè)棧共享存儲(chǔ)空間和提高效率，不存在棧滿上溢情況
鏈?zhǔn)酱鎯?chǔ)便于結(jié)點(diǎn)的插入刪除
入棧和出棧都在鏈表表頭進(jìn)行
對(duì)于帶不帶頭結(jié)點(diǎn)的鏈棧實(shí)現(xiàn)會(huì)有不同
每個(gè)元素需要1個(gè)存儲(chǔ)單元，每進(jìn)棧一次top+1，出棧一次top-1
單循環(huán)鏈表通過(guò)尾指針可以很方便找到表頭結(jié)點(diǎn)，沒(méi)有尾結(jié)點(diǎn)找需要花費(fèi)O(n)時(shí)間
隊(duì)列
先進(jìn)先出
只允許一端進(jìn)入另一端刪除
隊(duì)頭：允許刪除的一端，隊(duì)首
隊(duì)尾：允許插入的一端
操作
initQueue(&Q)初始化隊(duì)列
QueueEmpty(Q)判斷列空
EnQueue(&Q,&x)入隊(duì)，未滿將x加入成為新的隊(duì)尾
DeQueue(&Q,&x)出隊(duì)，非空刪除隊(duì)頭元素并用x返回
GetHead(Q,&x)讀隊(duì)頭元素，非空將隊(duì)頭元素賦值給x
順序存儲(chǔ)結(jié)構(gòu)
初始(隊(duì)空）：Q.front=Q.rear=0
循環(huán)隊(duì)列
把存儲(chǔ)隊(duì)列元素的表從邏輯上視為一個(gè)環(huán)
隊(duì)空：Q.front=Q.rear=0
隊(duì)滿：(Q.rear+1)%MaxSize==Q.front
隊(duì)列中元素個(gè)數(shù)：(Q.rear-Q.front+MaxSize)%MaxSize
鏈?zhǔn)酱鎯?chǔ)
隊(duì)列的鏈?zhǔn)奖硎痉Q為鏈隊(duì)列
實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針的隊(duì)尾指針的單鏈表
鏈隊(duì)列為空：Q.frontNull且Q.rearNull
不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列在操作上比較麻煩
單鏈表表示的鏈?zhǔn)疥?duì)列特別適合于數(shù)據(jù)元素變動(dòng)比較大的情形，不存在隊(duì)滿產(chǎn)生溢出問(wèn)題
雙端隊(duì)列
允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列
輸出受限的雙端隊(duì)列：一端只插入另一端允許插入刪除
輸入受限的雙端隊(duì)列：一端只刪除另一端允許插入刪除
1.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0…n]中，入隊(duì)操作為rear=(rear+1) mod maxsize,這里maxsize等于n+1
2.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[21]中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素，這里maxsize等于21
隊(duì)長(zhǎng)為**(rear-front+maxsize)%maxsize**
3.求值：
刪:front=(front+1)%個(gè)數(shù)
插:rear=(rear+1)%個(gè)數(shù)
4.鏈?zhǔn)酱鎯?chǔ)方式隊(duì)列的隊(duì)列進(jìn)行刪除操作時(shí)需要頭尾指針可能都要修改
棧和隊(duì)列的應(yīng)用
棧在括號(hào)匹配中的應(yīng)用
棧在表達(dá)式求值中的應(yīng)用
棧在遞歸中的應(yīng)用：效率低，代碼簡(jiǎn)單易于理解
將遞歸算法轉(zhuǎn)換為非遞歸算法，通常借助棧來(lái)實(shí)現(xiàn)
迷宮求解用的棧
隊(duì)列在層次遍歷中的應(yīng)用
隊(duì)列在計(jì)算機(jī)系統(tǒng)中的應(yīng)用
緩沖區(qū)、廣度優(yōu)先搜索圖用的隊(duì)列
數(shù)組
由n個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的有限序列
特殊矩陣的壓縮存儲(chǔ)
我懶……看大佬的哈哈哈哈文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-489999.html
數(shù)組詳細(xì)筆記文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-489999.html
到了這里，關(guān)于408數(shù)據(jù)結(jié)構(gòu)第三章的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
