1、棧和隊(duì)列及其應(yīng)用棧和隊(duì)列通常用來存儲程序執(zhí)行期間產(chǎn)牛的一些臨時信息。這兩種特殊表結(jié) 構(gòu)的共同特點(diǎn)是，只做插入和刪除，不做查找，而且所有的插入和刪除只在端點(diǎn) 進(jìn)行。棧是一種特殊的表結(jié)構(gòu)，滿足先進(jìn)后出策略(lifo: last in first out), 棧的插入和刪除操作只在同一端點(diǎn)進(jìn)行。可以進(jìn)行插入的端點(diǎn)叫棧頂(top),另一個端點(diǎn)叫棧底(bottom)。棧的插入操作又叫進(jìn)棧(push)或壓棧，棧刪除操作又叫退棧(pop)或?qū)鐥！＿J棧棧的結(jié)構(gòu)示意圖注意：進(jìn)棧和退棧可以不定期地、反復(fù)交替進(jìn)行。牛活中類似棧的應(yīng)用的例子：裝藥片的小圓桶，軍用子彈卡等。思考：假設(shè)有編號為1, 2, 3的3輛車，如果

2、按照編號為1, 2, 3的順序入 棧，那么可能的出棧順序有幾種情況？ ？ ？棧的存儲方式：1 順序存儲2.鏈?zhǔn)酱鎯５某Ｒ姴僮?順序存儲方式實(shí)現(xiàn))數(shù)組sm存儲一個棧(m代表?xiàng)５娜萘?，top變量指示棧頂指針(下標(biāo))。 m二 6 時:進(jìn)棧算法：/宏定義#define m 6define empty -1void pushs (int s, int &top)int x, k;cout«，z請輸入要進(jìn)棧的元素值x；cin>>x;辻(top 二二mt)cout<<棧已經(jīng)滿，進(jìn)棧失敗!z，<<endl; return;/s+top;top+;sto

3、p=x;cout<<x<<"已成功進(jìn)棧! /z<<endl;出棧算法：void pops(int s, int &top)int x, k;if (top二二empty)cout«/z棧已經(jīng)空，退棧失敗!，z«endl;return ;/x=stop-;x=stop;top;cout<<，z 已退棧頂元素，z<<x<<endl;課堂實(shí)踐：結(jié)合入棧和出棧算法完成入棧、出棧、顯示棧的當(dāng)前元素程序（stack, cpp） o隊(duì)又稱為隊(duì)列，是一種特殊的表結(jié)構(gòu)，滿足先來先服務(wù)策略（fif0:fi

4、rs tin first out）,隊(duì)的插入和刪除只在兩個端點(diǎn)進(jìn)行。允許插入的一端交隊(duì)尾（last），允許刪除的一端叫隊(duì)頭（first） o隊(duì)的插入和刪除操作分別稱為進(jìn)隊(duì)和出隊(duì)。隊(duì)結(jié)構(gòu)示意圖生活屮隊(duì)的例子很多：排隊(duì)上車或購物等。同棧的結(jié)構(gòu)一樣，進(jìn)隊(duì)和入隊(duì)操作是不定期地、反復(fù)地進(jìn)行的。隊(duì)的存儲方式：1 順序存儲2.鏈?zhǔn)酱鎯﹃?duì)的常見操作（順序存儲方式實(shí)現(xiàn)）（詳見板書）循環(huán)隊(duì)列（詳見板書）數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列棧和隊(duì)列的基礎(chǔ)知識棧：棧是一種特殊的表結(jié)構(gòu)，滿足先進(jìn)后出策略（lifo: last in first out）, 棧的插入和刪除操作只在同一端點(diǎn)進(jìn)行。棧的常見操作：入棧、岀棧（棧空和棧滿的判斷）隊(duì)

5、：隊(duì)又稱為隊(duì)列，是一種特殊的表結(jié)構(gòu)，滿足先來先服務(wù)策略（fifo:first in first out），隊(duì)的插入和刪除只在兩個端點(diǎn)進(jìn)行。隊(duì)的常見操作：入隊(duì)、出隊(duì)（隊(duì)空、隊(duì)滿的判斷）數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列簡單應(yīng)用文字輸入(enter. cpp)k問題描述h在文字輸入的過程中，出現(xiàn)輸入錯誤是不可避免的，所以需要給用戶提供一 個改正的方法。我們的方法是這樣的：用符號表示前一個字符無效，用符號表示 本行之前輸入的所有內(nèi)容無效。比如一個字符串“abcd$bcd”，它的實(shí)際內(nèi)容是“abcbcd”，字符串 uabc#abc$dn的實(shí)際內(nèi)容是“ad”。k輸入文件u輸入文件名：enter, in文件第一行是一個整

6、數(shù)n (1<7v<1oo),表示這個文本文件的行數(shù)。z后n 行，每行一個長長的字符串(長度不會超過10000),其中就包括'$'和 這樣的字符和一些英文字母，沒有其它的字符。k輸出文件u輸岀文件名：enter, out文件屮有個字符串，每個字符串一行，是輸入文件的最終結(jié)果。k樣例輸入d2abcd$bcdabc#abc$dk樣例輸出uabcbcd ad天使之城(ange1 cpp)k問題描述u天使城有一個火車站，每輛火車都從a方向駛?cè)胲囌荆谠購腷方向駛出車站。為了調(diào)度火車，火車站設(shè)有停放軌一一 道，可存放5輛火車。已知從a進(jìn)入車站順序?yàn)?、2、3o x 喝©

7、;h期糾1 現(xiàn)在給你一個調(diào)度方案，判斷是否可行，如果可行，輸出鯊今出站順序。h有以下幾種調(diào)度方法：日a. 將a上的頭一輛車駛出b方向b. 將a上的頭一輛車停入暫停軌道c. 將暫停軌道上最外面的車駛岀b方向k輸入文件輸入文件：angel, in第一行一個整數(shù)n (n<30)表示調(diào)度方案步驟數(shù)目。下一行一個字符串，有n個大寫字母，表示調(diào)度方法。k輸岀文件輸出文件：angel, out若不可行(暫停站滿了還停車、暫停站空了還出車)，則輸出一行“no”。若可行，輸出一行“yes”，再輸出若干行，每行一個整數(shù)，表示車出站序列。 k樣例輸入6abbccak樣例輸出uyes1324k樣例輸入5baca

8、ck樣例輸出hno銀行取款（bank cpp）k問題描述u在現(xiàn)代文明社會中，大家在諸如銀行辦理業(yè)務(wù)、車站買票等活動時都很文明 沒有插隊(duì)的現(xiàn)象，本著“先來先服務(wù)”的規(guī)矩。五一馬上到了，凡凡的爸爸打算上銀行去取點(diǎn)錢，帶著一向表現(xiàn)很好的凡凡 同學(xué)到海南旅游，凡凡的爸爸到銀行時發(fā)現(xiàn)很多人在辦理業(yè)務(wù)，凡凡的爸爸就自 覺地在排隊(duì)機(jī)上去了一個業(yè)務(wù)號碼，并焦急的等待著銀行柜臺叫自己的號 碼k輸入文件為輸入文件名：bank, in輸入中包含i （表示等待辦理業(yè)務(wù)）和顧客的序號；或者0 （表示辦理完業(yè)務(wù)的人離開）；輸入數(shù)據(jù)不超過100行。k輸出文件輸出文件名:bank, out輸岀銀行排隊(duì)中岀隊(duì)顧客序列，若隊(duì)列為空（沒人等待），則輸岀“none” k樣例輸入0i 1i 201 300