棧與隊(duì)列(ACM)

1、u線性結(jié)構(gòu)（順序表、棧、隊(duì)列）u非線性結(jié)構(gòu)圖（二叉樹、平衡二叉樹）u排序u查找 n 個(gè)人圍成一個(gè)圓圈，第個(gè)人圍成一個(gè)圓圈，第1個(gè)人從個(gè)人從1開始順時(shí)針開始順時(shí)針報(bào)數(shù)報(bào)數(shù), 報(bào)到報(bào)到m的人，令其出列。然后再?gòu)南乱坏娜耍钇涑隽?。然后再?gòu)南乱粋€(gè)人開始，從個(gè)人開始，從1順時(shí)針報(bào)數(shù)，報(bào)到第順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再個(gè)人，再令其出列，令其出列，如此下去，如此下去, 直到圓圈中只剩一直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)勝者。個(gè)人為止。此人即為優(yōu)勝者。 要求要求 輸入輸入 n 和和m, 輸出優(yōu)勝者輸出優(yōu)勝者 例如例如 n = 8 m = 3u#includeuusing namespace std;ust

2、ruct node /結(jié)點(diǎn)定義結(jié)點(diǎn)定義uint num; /人的編號(hào)人的編號(hào)unode *link;u;uvoid initial(node &circle, int n); / 初始化初始化uvoid solve(node &circle, int n, int m);u /求解過程求解過程u uint main()uint n, m;unode circle;uwhile(cin n m)uif(m = 1) /特殊處理特殊處理u cout n endl;u continue;u u initial(circle, n, m); u solve(circle, n, m);uureturn

3、 0;uuvoid initial(node &circle, int n)ucircle.num = 1; / 頭結(jié)點(diǎn)初始化頭結(jié)點(diǎn)初始化 ucircle.link = NULL;unode *r, *s;u r = &circle; /r始終指向尾結(jié)點(diǎn)始終指向尾結(jié)點(diǎn)ufor(int i = 2; i num = i;ur-link = s; /s將插入將插入r后后ur = s; /r指向結(jié)點(diǎn)指向結(jié)點(diǎn)suur-link = &circle; /尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)uuvoid solve(node &circle, int n, int m)unode *r, *p; ur = &

4、circle;ufor(int i = 1; i n; +i) /循環(huán)循環(huán)n - 1次次u for(int j = 2; j link; u p = r-link; /找到第找到第m個(gè)人個(gè)人pu r-link = p-link;u delete p; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)u r = r-link;uucout 優(yōu)勝者是優(yōu)勝者是 num endl;uuu報(bào)數(shù)問題u描述：u n個(gè)人圍成一個(gè)圈，每個(gè)人分別標(biāo)注為1、2、.、n，要求從1號(hào)從1開始報(bào)數(shù)，報(bào)到k的人出圈，接著下一個(gè)人又從1開始報(bào)數(shù)，如此循環(huán)，直到只剩最后一個(gè)人時(shí)，該人即為勝利者。例如當(dāng)n=10,k=4時(shí)，依次出列的人分別為4、8、2、7、3

5、、10，9、1、6、5，則5號(hào)位置的人為勝利者。給定n個(gè)人，請(qǐng)你編程計(jì)算出最后勝利者標(biāo)號(hào)數(shù)。u輸入：u 輸入包含若干個(gè)用例，每個(gè)用例為接受鍵盤輸入的兩個(gè)數(shù)n(1=n=1000000), k(1=k=50)，分別表示總?cè)藬?shù)及報(bào)到出圈數(shù)。輸入為“0 0“表示輸入用例結(jié)束。u輸出：u 每個(gè)用例用一行輸出最后勝利者的標(biāo)號(hào)數(shù)。u輸入樣例1：u1 1u10 4u0 0u輸出樣例1：u1u5u#include uusing namespace std;uint main()uuint n, m, i, s=0;uwhile(cinnm&n!=0&m!=0)uus=0;ufor (i=2; i=n; i+)

6、us=(s+m)%i;ucouts+1endl;uureturn 0;uuTOJ uTOJ 1153uTOJ 1547uTOJ 1601uTOJ 3070第二講第二講 數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu)棧具有一個(gè)逆序的特點(diǎn)，這便是棧的主要思想。棧具有一個(gè)逆序的特點(diǎn)，這便是棧的主要思想。uTOJ1036uZOJ1259upoj 1363 Railsu有一個(gè)車站，每天都會(huì)有N輛車進(jìn)站，進(jìn)站按從1N的順序進(jìn)站?，F(xiàn)在車站的站長(zhǎng)想讓這些火車按照特定的順序出站，問可以做到嗎？u某城市有一個(gè)火車站，其中的鐵路如圖所示某城市有一個(gè)火車站，其中的鐵路如圖所示，車站用來(lái)中轉(zhuǎn)車輛。，車站用來(lái)中轉(zhuǎn)車輛。u每輛火車都

7、從每輛火車都從A A方向駛?cè)胲囌荆購(gòu)姆较蝰側(cè)胲囌?，再?gòu)腂 B方向駛出車站，同時(shí)它方向駛出車站，同時(shí)它的車廂可以進(jìn)行重新組合。假設(shè)火車有的車廂可以進(jìn)行重新組合。假設(shè)火車有n n節(jié)車廂，分別按順序節(jié)車廂，分別按順序編號(hào)為編號(hào)為u負(fù)責(zé)車廂調(diào)度的工作人員需要知道能否使它以負(fù)責(zé)車廂調(diào)度的工作人員需要知道能否使它以 的順序從的順序從B B方向駛出。編寫程序，判斷是否得到制定的車廂順方向駛出。編寫程序，判斷是否得到制定的車廂順序。序。na aa.,21n.2 , 1n由于火車的調(diào)度過程符合由于火車的調(diào)度過程符合“后進(jìn)先出后進(jìn)先出”的特點(diǎn)的特點(diǎn), ,所以本題的模所以本題的模型是一個(gè)棧型是一個(gè)棧. .可以通過

8、簡(jiǎn)單模擬來(lái)判斷火車能否到達(dá)目標(biāo)狀態(tài)可以通過簡(jiǎn)單模擬來(lái)判斷火車能否到達(dá)目標(biāo)狀態(tài). .AB目標(biāo)序列 5 4 3 2 1 4 5 A站車廂321Stationy = 1 x = 4nx x表示表示A A站最前方車廂的編號(hào)站最前方車廂的編號(hào)ny y表示依照出棧序列表示依照出棧序列 下一個(gè)需要進(jìn)入下一個(gè)需要進(jìn)入B B站的車廂的序號(hào)站的車廂的序號(hào)n用棧用棧stackstack記錄當(dāng)前車站記錄當(dāng)前車站StationStation中的車廂中的車廂n初始時(shí)，初始時(shí)， , stack, stack為空棧為空棧 。na aa.,211, 0ayx如果如果 y=0, y=0, 那么火車調(diào)度成功那么火車調(diào)度成功否則如果

9、否則如果 x = y , x = y , 那么讓那么讓x x直接從直接從A A開進(jìn)開進(jìn)B B 否則如果否則如果stackstack不為空且不為空且 y=stacky=stack棧頂元素，棧頂元素， stackstack出棧出棧否則如果否則如果x 0,x 0,那么讓車廂駛?cè)肽敲醋屲噹側(cè)雜tack( stack( 入棧）入棧）否則否則 輸出無(wú)解輸出無(wú)解uTOJ 3072已知車廂的個(gè)數(shù)已知車廂的個(gè)數(shù)N , N , 給出所有可能的初始序列，使之給出所有可能的初始序列，使之能調(diào)度到目標(biāo)序列能調(diào)度到目標(biāo)序列 樣例樣例N=3N=3時(shí)，輸出時(shí)，輸出123123132132213213231231321321

10、n.2 , 1n生成所有生成所有 的排列，再依次判斷是否符合要求。的排列，再依次判斷是否符合要求。n判斷序列是否可行時(shí)調(diào)用上一題算法。判斷序列是否可行時(shí)調(diào)用上一題算法。n輸出可行解。輸出可行解。N=3N=3時(shí)時(shí)123123132132213213231231312312321321n.2 , 1uTOJ 1036 RailsuTOJ 1196 Web Navigation /POJ1028uTOJ 3072 Train OrderuPOJ 2082 Terrible Sets用棧來(lái)做（用棧來(lái)做（n)的算法的算法uPOJ 1686 Lazy Math Instructor中序表達(dá)式中序表達(dá)式uP

11、OJ 3250 u給出的序列中，如果給出的序列中，如果i k j 而且而且 hk hi hj，對(duì)，對(duì)i找出找出i到到j(luò)區(qū)間比區(qū)間比hi小的數(shù)的個(gè)數(shù)小的數(shù)的個(gè)數(shù)si。然后對(duì)每個(gè)。然后對(duì)每個(gè)i求和。求和。uWeb Navigationu在在POJ中，一道經(jīng)典的用到棧的基礎(chǔ)題目是中，一道經(jīng)典的用到棧的基礎(chǔ)題目是Web Navigation1，該題目要求模擬出瀏覽器前進(jìn)、后退、訪問的功能，用棧來(lái)表達(dá)該題目要求模擬出瀏覽器前進(jìn)、后退、訪問的功能，用棧來(lái)表達(dá)最為方便，訪問就是壓入一個(gè)元素進(jìn)棧，后退就是出棧，而前進(jìn)最為方便，訪問就是壓入一個(gè)元素進(jìn)棧，后退就是出棧，而前進(jìn)則是把后退出來(lái)的元素再按棧的規(guī)則彈出。

12、則是把后退出來(lái)的元素再按棧的規(guī)則彈出。u#include u#include u#include uusing namespace std;uint main()uustring cmd, url;ustack s1, s2; /定義了兩個(gè)棧定義了兩個(gè)棧u/棧棧1用作存儲(chǔ)操作隊(duì)列，而棧用作存儲(chǔ)操作隊(duì)列，而棧2則用作臨時(shí)保存棧則用作臨時(shí)保存棧1出棧的數(shù)據(jù)出棧的數(shù)據(jù)us1.push(/); /首頁(yè)壓棧首頁(yè)壓棧uwhile(cin cmd)uuif(cmd = VISIT) /訪問操作訪問操作uucin url;us1.push(url); /把訪問的地址壓入棧把訪

13、問的地址壓入棧1uwhile(!s2.empty() s2.pop(); /清空棧清空棧2u/想一想，為什么要清空棧想一想，為什么要清空棧2ucout s1.top() 1) /如果此次彈出后不會(huì)使得棧變空如果此次彈出后不會(huì)使得棧變空uus2.push(s1.top(); /把棧把棧1頂元素壓入棧頂元素壓入棧2us1.pop();ucout s1.top() endl;uuelseucout Ignored endl;uuelse if(cmd = FORWARD) /前進(jìn)操作前進(jìn)操作uuif(!s2.empty() /棧棧2有元素，意味著可以前進(jìn)有元素，意味著可以前進(jìn)uus1.push(s2

14、.top(); /把棧把棧2的頂端元素壓入棧的頂端元素壓入棧1ucout s2.top() endl;us2.pop(); /彈出棧彈出棧2的頂端元素的頂端元素uuelseucout Ignored endl;uuelse break;uureturn 0;u進(jìn)制轉(zhuǎn)換的時(shí)候每次將所求得的余數(shù)壓棧。進(jìn)制轉(zhuǎn)換的時(shí)候每次將所求得的余數(shù)壓棧。直到商為直到商為0。按順序取出來(lái)便是正確的轉(zhuǎn)換結(jié)果。按順序取出來(lái)便是正確的轉(zhuǎn)換結(jié)果。u標(biāo)準(zhǔn)輸入輸出標(biāo)準(zhǔn)輸入輸出u題目描述：題目描述：u數(shù)制轉(zhuǎn)換。數(shù)制轉(zhuǎn)換。(要求采用棧實(shí)現(xiàn)要求采用棧實(shí)現(xiàn),練習(xí)進(jìn)棧入棧函數(shù)的編寫練習(xí)進(jìn)棧入棧函數(shù)的編寫)u輸入：輸入：u輸入的第一行包含

15、兩個(gè)數(shù)輸入的第一行包含兩個(gè)數(shù),n,d un表示要轉(zhuǎn)換的數(shù)的個(gè)數(shù)表示要轉(zhuǎn)換的數(shù)的個(gè)數(shù)ud表示要轉(zhuǎn)換成的進(jìn)制數(shù)表示要轉(zhuǎn)換成的進(jìn)制數(shù) u接下來(lái)是接下來(lái)是n個(gè)十進(jìn)制數(shù)個(gè)十進(jìn)制數(shù)u u輸出：輸出：u對(duì)每一測(cè)試用例，用一行輸對(duì)每一測(cè)試用例，用一行輸u出數(shù)制轉(zhuǎn)換后的結(jié)果出數(shù)制轉(zhuǎn)換后的結(jié)果u輸入樣例：輸入樣例：u2 8u123u213u輸出樣例：輸出樣例：u173u325亂序的車廂在一條鐵軌上，壓入的車廂不能回到原軌道，希望在狹亂序的車廂在一條鐵軌上，壓入的車廂不能回到原軌道，希望在狹窄的空間里將其排成有序的序列。窄的空間里將其排成有序的序列。按順序掃描車廂，按順序掃描車廂，如果當(dāng)前的車廂為有序序列的需要車廂

16、，那么參與排隊(duì)去。如果當(dāng)前的車廂為有序序列的需要車廂，那么參與排隊(duì)去。否則，將其壓棧，由于車廂在棧內(nèi)必須有序，所以要找一個(gè)可以壓否則，將其壓棧，由于車廂在棧內(nèi)必須有序，所以要找一個(gè)可以壓并且棧頂元素與當(dāng)前車廂序號(hào)差小的棧壓。并且棧頂元素與當(dāng)前車廂序號(hào)差小的棧壓。如果沒有可以壓的棧，那么新開一個(gè)棧。如果沒有可以壓的棧，那么新開一個(gè)棧。開的棧數(shù)為最小用棧數(shù)。開的棧數(shù)為最小用棧數(shù)。三根柱子三根柱子A，B，C，在，在A上有從小到大放著一些碟子，碟子在柱子上有從小到大放著一些碟子，碟子在柱子上只能以小的壓在大的上面的形式存在，求如何使這些碟子的順序上只能以小的壓在大的上面的形式存在，求如何使這些碟子的順

17、序原封不動(dòng)的轉(zhuǎn)移到另外一跟柱子原封不動(dòng)的轉(zhuǎn)移到另外一跟柱子B上。上。同樣是同樣是3根柱子和一些盤子，變化的是盤子數(shù)是給定的。還是只能根柱子和一些盤子，變化的是盤子數(shù)是給定的。還是只能以小壓大的方式存在，但目標(biāo)狀態(tài)和初始狀態(tài)的順序是一樣的。以小壓大的方式存在，但目標(biāo)狀態(tài)和初始狀態(tài)的順序是一樣的。Poj3601對(duì)于一個(gè)給定的黑箱子開關(guān)盒，給定配對(duì)的針腳，判斷這樣的線可對(duì)于一個(gè)給定的黑箱子開關(guān)盒，給定配對(duì)的針腳，判斷這樣的線可不可以在一個(gè)平面的電路板上布下。（不相交）不可以在一個(gè)平面的電路板上布下。（不相交）從某點(diǎn)順時(shí)針開始，從某點(diǎn)順時(shí)針開始，當(dāng)前元素和棧頂元素可以配對(duì)，那么彈出棧頂元素。當(dāng)前元素和

18、棧頂元素可以配對(duì)，那么彈出棧頂元素。當(dāng)前元素和棧頂元素不能配對(duì)，那么將當(dāng)前元素壓棧。當(dāng)前元素和棧頂元素不能配對(duì)，那么將當(dāng)前元素壓棧。最終棧不空就無(wú)解。最終棧不空就無(wú)解。回溯深搜的時(shí)候系統(tǒng)就是用棧來(lái)實(shí)現(xiàn)的。回溯深搜的時(shí)候系統(tǒng)就是用棧來(lái)實(shí)現(xiàn)的。可以自己模擬一下試試。可以自己模擬一下試試。后續(xù)表達(dá)式后續(xù)表達(dá)式(逆波蘭式逆波蘭式)的特點(diǎn)：沒有括號(hào)。的特點(diǎn)：沒有括號(hào)。從前向后掃，從前向后掃，遇到操作數(shù)壓棧；遇到操作數(shù)壓棧；遇到操作符，從棧中取出遇到操作符，從棧中取出2個(gè)操作數(shù)運(yùn)算，結(jié)果壓棧。個(gè)操作數(shù)運(yùn)算，結(jié)果壓棧。最終棧中所剩的數(shù)為結(jié)果。最終棧中所剩的數(shù)為結(jié)果。我們先來(lái)定義運(yùn)算符的優(yōu)先級(jí)：我們先來(lái)定義運(yùn)

19、算符的優(yōu)先級(jí)：(+,-*,/,%從上到下依次升高從上到下依次升高準(zhǔn)備準(zhǔn)備2個(gè)棧，一個(gè)專門存放運(yùn)算符，另一個(gè)專門存放操作數(shù)。個(gè)棧，一個(gè)專門存放運(yùn)算符，另一個(gè)專門存放操作數(shù)。1.遇到遇到)，那么退棧計(jì)算到，那么退棧計(jì)算到(為止為止.結(jié)果壓棧。結(jié)果壓棧。2.遇到運(yùn)算數(shù)遇到運(yùn)算數(shù).那么壓棧。那么壓棧。3.如果當(dāng)前運(yùn)算符優(yōu)先級(jí)低于棧頂運(yùn)算符如果當(dāng)前運(yùn)算符優(yōu)先級(jí)低于棧頂運(yùn)算符.那么計(jì)算棧頂運(yùn)算符并將那么計(jì)算棧頂運(yùn)算符并將結(jié)果壓棧結(jié)果壓棧.4.否則壓棧否則壓棧.定義優(yōu)先級(jí)：定義優(yōu)先級(jí)：(大于左邊所有，小于右邊所有大于左邊所有，小于右邊所有-,+*,/,%從左向右，從左向右，定義當(dāng)前運(yùn)算符定義當(dāng)前運(yùn)算符now

20、之前運(yùn)算符之前運(yùn)算符last.遇到數(shù)字直接輸出。遇到數(shù)字直接輸出。.遇到遇到)就把之前的全部輸出。就把之前的全部輸出。.如果如果now優(yōu)先級(jí)高于優(yōu)先級(jí)高于last運(yùn)算符運(yùn)算符.那么輸出那么輸出now。Last不變。不變。.否則輸出否則輸出last。last=now。還可以通過樹的方式建立表達(dá)式樹來(lái)轉(zhuǎn)換還可以通過樹的方式建立表達(dá)式樹來(lái)轉(zhuǎn)換u標(biāo)準(zhǔn)輸入輸出u題目描述：u小學(xué)求算式問題。要求采用棧實(shí)現(xiàn)。u輸入：u輸入第一行為用例個(gè)數(shù)n。u接下來(lái)n個(gè)表達(dá)式。u u輸出：u對(duì)每一個(gè)用例的表達(dá)式，輸出其結(jié)果。u輸入樣例：u3u2+5u4+2*3-10/5u3*7-2u輸出樣例：u7u8u19u題目描述：題目描述：u根據(jù)給定的空間構(gòu)造順序循環(huán)隊(duì)列，規(guī)定隊(duì)滿處理方法為少用一個(gè)元根據(jù)給定的空間構(gòu)造順序循環(huán)隊(duì)列，規(guī)定隊(duì)滿處理方法為少用一個(gè)元素空間。例如，給定素空間。例如，給定5個(gè)元素空間構(gòu)造循環(huán)隊(duì)列，則只能存放個(gè)元素空間構(gòu)造循環(huán)隊(duì)列，則只能存放4個(gè)元素個(gè)元素。試根據(jù)入隊(duì)及出隊(duì)操作判斷隊(duì)列最后的元素存放情況，并輸出最后。試根據(jù)入隊(duì)及出隊(duì)操作判斷隊(duì)列最后的元素存放情況，并輸出最后隊(duì)列中的元素值，即完成給定入隊(duì)及出列操作后一次性全部出隊(duì)的元隊(duì)列中的元素值，即完成給定入