數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)

數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第2頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3順序棧 用向量作為存儲(chǔ)結(jié)構(gòu)，可用一維數(shù)組s[1:m] 表示。

m－棧的最大容量。 Top－棧頂指示器。top=0，棧空；top=m，棧滿(mǎn)。2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算a1a2……top12a1a2……123top進(jìn)棧：top+1a1a2……12退棧：top-1topa1a2a3……am棧滿(mǎn)top……0top?？諗?shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第3頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算4插入（進(jìn)棧）：先令top加“1”，再將元素送入s[top]中。當(dāng)top=m時(shí)若再有元素進(jìn)棧，則產(chǎn)生“上溢”。算法如下：Push(s,m,top,x){

if(top=m){ “上溢”;return; }

top++;s[top]<-x;return;}2.3棧與隊(duì)刪除（退棧）：只要將top減“1”即可。算法如下：Pop(s,top,y)

{

if(top=0){ “下溢”; return; } y<-s[top];top--;

return;

}數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第4頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算5鏈棧 鏈棧是用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，top為棧頂指 針，指示棧頂元素位置，若top=nil,則表示棧 空。鏈棧一般不會(huì)出現(xiàn)上溢，除非內(nèi)存中已不 存在可用空間。2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算top^棧底top空棧數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第5頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算6鏈棧的插入（進(jìn)棧）：鏈棧的刪除（退棧）：top┄x^pdata(p)<-x; next(p)<-top;Top<-p;top┄^P<-top;top<-next(top);RET(p);數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第6頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算74.對(duì)頂棧2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算棧底1a1a2a3a4a5棧底2a1a2top1top2特點(diǎn)：共享?xiàng)？臻g 若A(1:m),則每棧最大空間>m/2數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第7頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算85.棧的應(yīng)用

(1)

表達(dá)式求值（用于高級(jí)語(yǔ)言的編譯程序）

運(yùn)算符：**/*+-; 優(yōu)先數(shù)：3221102.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算小括號(hào)優(yōu)先數(shù)：θ1 θ2

(

<其它符號(hào)，=“)”

(

>其它符號(hào))

>其它符號(hào)

)

<其它符號(hào)數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第8頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算9

需建立兩個(gè)棧：操作數(shù)(NS)、運(yùn)算符(OS)。

算法思想：置NS為空，“；”作為OS的棧底元素。自左至右掃描表達(dá)式：①若為操作數(shù)，將其壓入NS棧②若為運(yùn)算符，與OS棧頂元素比較優(yōu)先級(jí)：>OS棧頂，則將當(dāng)前運(yùn)算符壓入OS棧。<=OS棧頂，則從NS棧中彈出兩個(gè)操作數(shù)x、y，再?gòu)腛S棧中彈出一個(gè)運(yùn)算符θ，構(gòu)成一條機(jī)器指令：xθy→T，將結(jié)果T送入NS棧。=“；”，且OS棧頂也為“；”，則表示表達(dá)式處理結(jié)束，此時(shí)NS棧頂?shù)脑丶礊榇吮磉_(dá)式的值。(1)

表達(dá)式求值數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第9頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算10

舉例：設(shè)表達(dá)式為：A/B**C+D;過(guò)程為：CBA**/;DT2+;B**C-->T1T1A/;T2+

D-->T3T3;;A/T1-->T2T2得到表達(dá)式的值T32.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第10頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算11

過(guò)程嵌套－－多重嵌套時(shí)，用棧將各層斷點(diǎn)信息依次入棧，當(dāng)各層子過(guò)程返回時(shí)，以相反的次序從棧頂取出（FILO,or,LIFO）2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算r主過(guò)程rstrsrstrsr子程A子程B子程C數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第11頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算12

遞歸調(diào)用－－一個(gè)過(guò)程通過(guò)過(guò)程調(diào)用語(yǔ)句 直接或間接地調(diào)用自己的過(guò)程。2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算直接遞歸程序ABegin.A.End程序A程序BBegin.B.EndBegin.A.End間接遞歸數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第12頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算13(3)

回溯求解算法 1）問(wèn)題描述：設(shè)有n件體積分別為w1,w2,...,wn的物品和一個(gè)能裝載總體積為T(mén)的背包，要求從n件物品中挑選出若干件物品，其體積之和恰好裝滿(mǎn)背包。若能，則背包問(wèn)題有解，否則無(wú)解。 2）解決方法：先將n件物品順序排列，依次裝入背包，每裝入一件即檢查當(dāng)時(shí)包內(nèi)物品體積是否超過(guò)T，若裝入該件物品后不超過(guò)背包容2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算5.棧的應(yīng)用數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第13頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算14 量T，則裝入，否則棄之取下一個(gè)，直到裝滿(mǎn)背包為止。若在裝入若干物品后背包未滿(mǎn)，但又無(wú)其它物品可選時(shí)，說(shuō)明已裝入背包內(nèi)的物品組合不合適，需從背包中取出最后裝入的物品，繼續(xù)在其它未裝入物品中挑選，如此重復(fù)直到裝滿(mǎn)背包（有解）或無(wú)合適物品可選（無(wú)解）。 3）分析：設(shè)一維數(shù)組W[n]用來(lái)存放n件物品的體積，棧S[n]用來(lái)存放放入背包內(nèi)物品的序號(hào)，2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第14頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算15

T為背包能容納的體積，i為待選物品序號(hào)。每進(jìn)棧一件物品，就從T中減去該物品的體積，若T-W[i]≥0，則該物品可選，若T-W[i]<0，則該物品不可選，若i>n，則需退棧，若此時(shí)?？眨瑒t說(shuō)明無(wú)解。2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第15頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算16 4）算法描述

Pack(T,n,W,S,top)

{

top=0;i=1;//初始化

while(T>0&&i<=n){

if(T-W[i]==0||(T-W[i]>0&&i<n)){//可選

top++;S[top]=i;T=T-W[i];

}

if(T==0)return(1);//有解

else{//退棧

if(i==n&&top>0){i=S[top];top--;T+=W[i];}

i++;//取下一個(gè)

}

return(0);

}2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第16頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算172.3.1棧的結(jié)構(gòu)和運(yùn)算2.3棧與隊(duì) 5）舉例 若T=10，W=(4,7,3,5,4,2)，棧的變化如下：473542Wi初始狀態(tài)StopT=10473542Wi414StopT=1473542i11topT=6473542i313topT=3473542i回溯41topT=6473542i回溯51topT=6473542i515topT=2473542i6156topT=0數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第17頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算185.棧的應(yīng)用

(4)

改變輸出序列1）一個(gè)適當(dāng)大小的棧，輸入序列為ABCDE，經(jīng)過(guò)一次壓棧和退棧操作，能否得到如下序列：

I:ABCDE II:EABCD2）將上述序列改為ABCDEF，經(jīng)一次退壓棧，能否得到以下序列？如果不能，經(jīng)過(guò)兩次退壓棧操作能否得到？

I:CBEFDA II:AEDFBC2.3棧與隊(duì)2.3.1棧的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第18頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算192.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算隊(duì)的定義 只允許在表的一端進(jìn)行插入，在表的另一 端進(jìn)行刪除的線(xiàn)性表。

隊(duì)尾－允許插入的一端(rear)

隊(duì)首－允許刪除的一端(front)2.3棧與隊(duì)rearfront隊(duì)中元素按a1,a2,…,an次序入隊(duì)和出隊(duì)。 隊(duì)的操作特點(diǎn)：先進(jìn)先出（FIFO）；

n=0時(shí)稱(chēng)為空隊(duì)。隊(duì)的存儲(chǔ)結(jié)構(gòu)：順序和鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第19頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算202.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算2.3棧與隊(duì)順序隊(duì)

(1)單向隊(duì)列 用一維數(shù)組Q[1:m]表示。m為隊(duì)的最大容量。隊(duì)空:rear=front（=0）進(jìn)隊(duì)：rear+1出隊(duì)：front＋1假溢出：rear=m,front!=0 (rear=m，front=0真滿(mǎn))r=0f=0初態(tài)a3a2a1r=3f=0進(jìn)隊(duì)a3a2r=3f=1出隊(duì)r=3f=3隊(duì)空a5a4a3a2a1r=5f=0隊(duì)滿(mǎn)a5a4r=5f=3假溢出數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第20頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算212.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算2.3棧與隊(duì)為避免假溢出的發(fā)生，將隊(duì)首和隊(duì)尾連接起來(lái)，形成頭尾相接的環(huán)形隊(duì)列，稱(chēng)循環(huán)隊(duì)列，用CQ[0:m-1]表示。(2)循環(huán)隊(duì)列（環(huán)形隊(duì)列）rear=3front=551

42

3a1a2a3數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第21頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算22frontrear01234。。

m-1初態(tài):rear=front=m-1frontrear01234。。

m-1進(jìn)隊(duì)a1a2a3a4出隊(duì)frontrear01234。。

m-1a3a4frontrear01234。。

m-1。。隊(duì)滿(mǎn):rear<-(rear+1)MODmfront=reara3a4a5am

.

.x01234

m-1隊(duì)空:rear=frontfrontrear數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第22頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算23

插入

AddCQ(CQ,m,front,rear,x)

{

rear<-(rear+1)MODm;

if(front==rear)return;//隊(duì)滿(mǎn)

CQ[rear]<-x;

return;

}//先找插入位置，再判斷賦值2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算frontrear01234。。

m-1進(jìn)隊(duì)a1a2a3a4數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第23頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算24

刪除

DelCQ(CQ,m,front,rear,y)

{

if(front==rear)return;//隊(duì)空

front<-(front+1)MODm;

y<-CQ[front];

return;

}//先判斷，后找刪除位置2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算出隊(duì)frontrear01234。。

m-1a3a4數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第24頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算25

說(shuō)明

1）循環(huán)隊(duì)列中判斷隊(duì)空和隊(duì)滿(mǎn)的條件： 隊(duì)空：front==rear

隊(duì)滿(mǎn)：(rear+1)MODm==front

2）在循環(huán)隊(duì)列中永遠(yuǎn)會(huì)空一個(gè)位置，這是為 了判別隊(duì)空和隊(duì)滿(mǎn)而造成的。 3）當(dāng)前隊(duì)列中的元素個(gè)數(shù)：

(rear-front+m)%m2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第25頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算262.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算2.3棧與隊(duì)允許在兩端進(jìn)行插入和刪除的線(xiàn)性表。(3)雙向隊(duì)列1231456m……leftright左端滿(mǎn)：left=1右端滿(mǎn)：right=m特殊的雙向隊(duì)列：※棧：

※限制輸入：

※限制輸出：數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第26頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算27例1：雙向隊(duì)列輸入序列為ABCDE，則不能得到的序 列是： EBCAD,EBCDA,EACBD, EACDB,DACBE,DACBE例2：輸入序列為ABCD，輸入受限和輸出受限雙向 隊(duì)列都得不到的序列是： ＤＢＣＡ數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第27頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算28鏈隊(duì) 采用鏈表結(jié)構(gòu)表示的隊(duì)列。

front:指向頭結(jié)點(diǎn)

rear：指向尾結(jié)點(diǎn)^frontrearrear空隊(duì)2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算

fronta1

an^rearreara2

……an^a2

a2

數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第28頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算29

插入(插在鏈尾)

AddLink(front,rear,x)

{

GETNODE(p);//申請(qǐng)結(jié)點(diǎn)

data(p)=x;//結(jié)點(diǎn)賦值

next(p)<-nil;

next(rear)<-p;

rear<-p;//修改尾指針

}2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算

x^frontrearrearx入隊(duì)

frontx^y^rearreary入隊(duì)rearrearp數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第29頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算30

刪除（刪除第一個(gè)結(jié)點(diǎn)）

DelLink(front,rear,x)

{

if(front==rear)return;//隊(duì)空

x<-data(next(front);

next(front)<-next(next(front);

if(next(front)=nil)rear<-front;

return;

}2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算

frontxy^rearrearx出隊(duì)數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第30頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算31隊(duì)的應(yīng)用

FIFO原則－－模擬排隊(duì)問(wèn)題。 多道程序中的CPU管理

在只有一個(gè)CPU的條件下，多個(gè)用戶(hù)共同使用計(jì)算機(jī)，隊(duì)列在實(shí)現(xiàn)合理分配CPU中起重要作用。操作系統(tǒng)可作如下處理： 1）當(dāng)一個(gè)用戶(hù)請(qǐng)求CPU時(shí)，它就進(jìn)入使用CPU的隊(duì)列。2.3棧與隊(duì)2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)全文共36頁(yè)，當(dāng)前為第31頁(yè)。第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算32

2）在此隊(duì)列首部的用戶(hù)是當(dāng)前CPU的使用者，并且在整個(gè)CPU時(shí)間周期內(nèi)繼續(xù)留在隊(duì)列的首部。 3）當(dāng)一個(gè)用戶(hù)完成了它的現(xiàn)行請(qǐng)求CPU的時(shí)間周期后，就