第三章 棧與隊(duì)列
一、棧
1.定義：只允許一端進(jìn)行插入和刪除的線性表，結(jié)構(gòu)與手槍的彈夾差不多，可以作為實(shí)現(xiàn)遞歸函數(shù)（調(diào)用和返回都是后進(jìn)先出）調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)；
- 棧頂：允許插入刪除的那端；
- 棧底：固定的，不允許插入或刪除；
- 空棧：不含元素；
2.特點(diǎn)：后進(jìn)先出；
3.操作：入棧（push）、出棧（pop）
4.應(yīng)用：遞歸、進(jìn)制轉(zhuǎn)換、迷宮求解、括號匹配。
5.棧的順序存儲（順序棧）
- 定義：利用一組地址連續(xù)的存儲單位存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)用一指針指示棧頂位置；
- 棧頂指針：S.top，初始值=-1，棧頂元素S.data[S.top]； 進(jìn)棧操作：棧不滿時(shí)，棧頂指針+1，再送棧到棧頂元素；
- 出棧操作：棧非空時(shí)，先取棧頂元素值，再將棧頂指針-1；
- ?？諚l件：S.top=-1；棧滿條件：S.top==MaxSize-1；棧長：S.top+1。
6.共享?xiàng)?/li> - 定義：兩共享?xiàng)９蚕硪粋€(gè)一維數(shù)組空間，兩個(gè)棧頂指針都指向棧頂元素，top=-1時(shí)0號棧為空，top1=MaxSize時(shí)1號棧為空；當(dāng)兩棧指針相鄰top1-top0=1時(shí)，滿棧；共享?xiàng)Ｊ菫榱烁玫睦么鎯臻g，兩個(gè)棧的空間相互調(diào)節(jié)，只有整個(gè)存儲空間都被占滿時(shí)才發(fā)生上溢。
7.鏈棧
- 定義：采用鏈?zhǔn)酱鎯Φ臈＃阌诙鄠€(gè)棧共享存儲空間和提高效率，且不存在棧滿上溢問題，采用單鏈表實(shí)現(xiàn)，所有操作都在單鏈表表頭進(jìn)行，操作與鏈表相似；
二、隊(duì)列
1.定義：簡稱隊(duì)，一種操作受限制的線性表，只允許在表的一端插入，在表另一端刪除。
- 隊(duì)頭：允許刪除的一端，隊(duì)頭指針指向隊(duì)頭元素；
- 隊(duì)尾：允許插入的一端，隊(duì)尾指針指向隊(duì)尾元素下一個(gè)位置；
- 空隊(duì)列：無元素 ；
- 初始條件（隊(duì)空條件）：Q.frontQ.rear0，front隊(duì)頭，rear隊(duì)尾;
- 假溢出：一維數(shù)組隊(duì)列的尾指針已達(dá)到數(shù)組上界，不能入隊(duì)，其實(shí)數(shù)組中還有空位置；
2.特點(diǎn)：先進(jìn)先出（怎么進(jìn)怎么出）；
3.應(yīng)用：緩沖區(qū)、頁面替換算法；
4.操作：進(jìn)隊(duì)（隊(duì)不滿時(shí)，先送值到隊(duì)尾元素，隊(duì)尾指針+1）；出隊(duì)（隊(duì)不空時(shí)，先取隊(duì)頭元素值，隊(duì)頭指針+1）；
5.循環(huán)隊(duì)列：把存儲隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，循環(huán)隊(duì)列的引入是為了防止假溢出；
文章來源：http://www.zghlxwxcb.cn/news/detail-607343.html
- 初始時(shí)：Q.front=Q.rear=0;
- 隊(duì)首指針進(jìn)1（出隊(duì)）：Q.front=(Q.front+1)%MaxSize;
- 隊(duì)尾指針進(jìn)1（入隊(duì)）：Q.rear=(Q.rear+1)%MaxSize;
- 隊(duì)列長度（隊(duì)列中元素個(gè)數(shù)）：(Q.rear-Q.front+MaxSize)%MaxSize【(尾-頭+M)%M】；
- 隊(duì)空：Q.frontQ.rear0；
- 隊(duì)滿：(Q.rear+1)%MaxSize==Q.front；
- 出隊(duì)入隊(duì)指針按順時(shí)針進(jìn)1；
- 例題：循環(huán)隊(duì)列存儲在數(shù)組A[0…n]中，則入隊(duì)操作為rear=(rear+1)mod(n+1)。
6.鏈隊(duì)列：同時(shí)帶隊(duì)頭指針和隊(duì)尾指針的單鏈表，無假溢出現(xiàn)象；
7.雙端隊(duì)列：允許兩邊都可以入隊(duì)和出隊(duì)。文章來源地址http://www.zghlxwxcb.cn/news/detail-607343.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)【棧和隊(duì)列】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
