數據結構之隊列王桐林壽光現代中學2009.8濰坊市2009信息學奧林匹克夏令營數據結構知識簡單回顧數據結構（datastructure）是相互之間存在一種或多種特定關系的數據元素的集合。是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。

數據結構的內涵“操作”的對象：數據。數據與數據間的關系。針對數據的基本操作。數據結構的形式定義

data_structure=(D,S)D:數據元素的有限集；S:Ｄ上關系的有限集；邏輯結構圖例數據元素間的關系結構名特性數據元素屬于或不屬于集合集合結構松散；用其他結構代替數據元素一個對一個線性結構結構簡單數據元素一個對多個樹形結構結構復雜數據元素多個對多個圖結構結構復雜物理結構

1、順序結構：借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。邏輯上關聯的數據元素，物理存儲結構中相鄰。

——數組2、鏈式結構：借助元素存儲地址的指針(pointer）表示數據元素之間的邏輯關系。邏輯上關聯的數據元素，物理存儲結構中不一定相鄰。——指針（動態存儲）邏輯結構、物理結構密切相關算法的設計取決于所選定的邏輯結構，算法的實現依賴于所采用的存儲結構。線性表由n個數據元素的有限序列除頭元素外，每個元素都有一個前趨除尾元素外，每個元素都有一個后繼ABCD棧棧（堆棧）是一種受限的線性表。其所有的插入和刪除操作均限定在線性表的一端進行，允許插入和刪除的一端稱為棧頂(表尾)，不允許插入和刪除的一端稱為棧底(表頭)。棧又稱為后進先出(LastInFirstOut，簡稱LIFO)表。棧與棧的順序存儲棧S順序存儲棧的實現（一）Constm=棧表目數的上限；Typestack=array[1..m]ofstype；{棧類型}Vars：stack；{棧}top：integer；{棧頂指針}

棧的實現（二）constm=棧表目數的上限；

typestack=recordelem:array[1..m]ofelemtp;top:0..m;{棧頂指針}end;Vars：stack；{棧}棧的基本操作初始化（init）、進棧（push）、出棧（pop）、讀取棧頂元素（top）、判斷棧是否為空或已滿。。棧的典型應用表達式求值括號區配隊列在日常生活中的排隊現象：購物、訂票、打飯、候車排隊所遵循的原則是“先來先服務”，后來者總是加到隊尾，排頭者總是先離開隊伍。隊列就是從日常生活中的排隊現象抽象出來的。隊列的定義隊列也是一種受限的線性表。它的所有插入都在隊列的一端進行，所有刪除都在另一端進行。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。隊列的插入和刪除我們稱為入隊和出隊，新元素入隊就成為新的隊尾元素，刪除元素后，其后繼元素成為新的隊首元素。

隊列是一種先進先出(FIFO)的線性表front>=rear，則隊列空;front<rear，則隊列非空。隊列的存儲隊列可以采用順序存儲結構和鏈式存儲結構我們一般采用順序存儲結構來定義隊列

——數組abcdrf空1、隊列的順序存儲（1）借助記錄類型來定義：constmaxn=xxxx;//隊列的最大長度typequeue=record

data:array[1..maxn]ofqtype;//qtype表示隊列元素的數據類型

front,rear:1..maxn//隊首指針和隊尾指針

end;varq:queue;（2）實際編程中可以直接定義成如下格式：constmaxn=xxxx;//隊列的最大長度var

q:array[1..maxn]ofqtype;//隊列front,rear:1..maxn;//隊首指針和隊尾指針2、隊列的鏈式存儲同棧一樣，隊列也可以采用鏈式存儲。隊列的基本操作初始化入隊出隊1、隊列的初始化或置空將隊首指針和隊尾指針皆置為0。

proceduresetnull；front:=0;rear:=0end；fr

0123……2、入隊add(x)，也稱為進隊首先判斷隊列q是否已滿，若未滿，則后移隊尾指針，并在隊列的尾端插入元素x。

procedureadd(x:qtype)；

beginifrear=maxnthenwriteln('queuefull!');haltend//隊滿

elsebeginrear:=rear+1；//后移隊尾指針q[rear]:=x；//插入元素xend；

end；Arf3、出隊del首先判斷隊列q是否已空，若未空，則后移隊首指針，并取出隊列q的隊首元素。

functiondel；

beginiffront=rearthenwriteln('queueempty!');haltend//隊空

elsebeginfront:=front+1;//后移隊首指針del:=q[front]；//取出隊首元素

end;end；bcdfr如果僅完成刪除操作，則只需要后移隊首指針（front:=front+1）即可。小練習①已知隊列(13，2，11，34，41，77，5，7，18，26，15)，第一個進入隊列的元素是13，則第五個出隊列的元素是（

）。(NOIP9)A）5

B）41

C）77

D）13

E）18

小練習②設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4，e5，e6依次通過棧S，一個元素出棧后即進入隊列Q，若出隊的順序為e2，e4，e3，e6，e5，e1，則棧S的容量至少應該為（）。(NOIP8)A）2B）3C）4D）5溢出什么是溢出？假溢出由于隊列只能在一端插入，在另一端刪除，因此隨著入隊及出隊運算的不斷進行，就會出現一種有別于棧的情形：隊列在數組中不斷地向隊尾方向移動，而在隊首的前面產生一片不能利用的空閑存儲區，最后會導致當尾指針指向數組最后一個位置（即r=max）而不能再加入元素時，存儲空間的前部卻有一片存儲區無端浪費，這種現象稱為“假溢出”。克服假溢出的方法有兩種一種是將隊列中的所有元素均向低地址區移動，顯然這種方法是很浪費時間的；另一種方法是將數組存儲區看成是一個首尾相接的環形區域。當存放到max地址后，下一個地址就“翻轉”為１。在結構上采用這種技巧來存儲的隊列稱為循環隊列。循環隊列隊列的應用例7-3細胞個數【試題描述】一矩形陣列由數字0到9組成,數字1到9代表細胞,細胞的定義為沿細胞數字上下左右還是細胞數字則為同一細胞,求給定矩形陣列的細胞個數。【輸入】整數m,n（第一行）m<50,n<80；矩陣(m行，n列)。【輸出】細胞的個數。【樣例輸入】410

0234500067

1034560500

2045600671

0000000089【樣例輸出】40234500067

1034560500

2045600671

0000000089共4個細胞算法步驟：1、從文件中讀入m*n矩陣，將其轉換為0、1矩陣存入pic數組中；1表示細胞，0表示無細胞

2、沿pic數組矩陣從上到下，從左到右，找到遇到的第一個細胞；將細胞的位置入隊h，并沿其上、下、左、右四個方向上搜索，如果遇到細胞(pic[I,j]=1)則將其位置入隊，入隊后的位置pic[I,j]數組置為0；

3、將h隊的隊頭出隊，沿其上、下、左、右四個方向上搜索，如果遇到細胞則將其位置入隊，入隊后的位置pic數組置為0；

4、重復3，直至h隊空為止，則此時找出了一個細胞；

5、重復2，直至矩陣找不到細胞；

6、輸出找到的細胞數。參考程序constdx:array[1..4]of-1..1=(-1,0,1,0);//橫坐標:左，下，右，上dy:array[1..4]of-1..1=(0,1,0,-1);//縱坐標:左，下，右，上vars:string;a:array[1..50,1..80]of0..1;//存儲矩陣的數組，0:無細胞；1：有細胞

m,n,i,j,num:integer;h:array[1..4000,1..2]ofbyte;//隊列：存細胞的坐標，1：行；2：列proceduretry(p,q:integer);//處理坐標（p,q）的細胞

vari,t,w,x,y:integer;begininc(num);//細胞數量加1a[p,q]:=0;t:=1;//隊頭

w:=1;//隊尾

h[1,1]:=p;h[1,2]:=q;//遇到的第一個細胞入隊

repeatfori:=1to4do//沿細胞的上下左右四個方向搜索細胞

beginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x>0)and(x<=m)and(y>0)and(y<=n)and(a[x,y]=1)thenbegininc(w);h[w,1]:=x;h[w,2]:=y;a[x,y]:=0;end;//為細胞的入隊

end;inc(t);//隊頭指針加1，出隊

untilt>w;//直至隊空為止

end;beginfillchar(a,sizeof(a),0);//初始化數組

fillchar(h,sizeof(h),0);//初始化隊列

num:=0;readln(m,n);fori:=1tomdo//讀入矩陣

beginreadln(s);forj:=1tondoifs[j]='0'thena[i,j]:=0elsea[i,j]:=1;end;fori:=1tomdoforj:=1tondoifa[i,j]=1thentry(i,j);//在矩陣中尋找細胞

writeln(num);//輸出細胞個數end.廣度優先搜索算法（bfs）1、適合的題目類型：

1）、求從給定初始狀態到目標狀態最少需要的步數。

2）、給定初始狀態，經過k步后能夠到達哪些狀態。2、利用的數據結構：隊列。3、狀態的最大值：決定隊列的大小（非常重要）4、隊列里需要記住哪些狀態：一般使用記錄數據類型。5、狀態的轉移：不能遺漏。6、狀態的判重：避免重復進入隊列。從初始結點開始，應用算符生成第一層結點，檢查目標結點是否在其中出現，若沒有，再用算符將第一層結點逐一擴展，得第二層結點，逐一檢查第二層中是否包含目標結點。若沒有，依次擴展、檢查……直到發現目標結點為止。這就是所謂的廣度優先搜索。abcdefjk用隊列的數據結構來存儲搜索過程中產生的結點，取隊頭元素擴展，產生的結點插入隊尾。Bfs的基本框架：初始化；建立數據庫（隊列）；初始狀態進入隊列；f=0;隊列的首指針；r=1;隊列的尾指針(開始時指向初始狀態)；q[1];初始結點;While（f<r）do{還有未擴展的結點，隊列不空}BeginInc（f）；{移動隊列的首指針：出隊列}

記錄f狀態；

Fori=1tomethoddo{按規則擴展下一層新的子結點}Begin

生成新的結點;If新結點是目標結點then輸出目標，搜索結束；

If新結點是以前沒出現過then保存新結點(入隊)；

EndEnd；【問題描述：】在n*n的棋盤上有一匹馬在第x行第y列的格子上。棋盤上有些格子上有障礙物，馬不能達到有障礙物的格子。已知馬在棋盤中的走法按“日“字8個方向可走，如下圖所示：問：哪些格子能到達，到達這些格子的最小步數是多少。【輸入：】第一行:n（n<=100）,x,y

(馬的開始位置)。接下來n行為棋盤的描述：“-“為空格子，”+“表示該格子有障礙物。【輸出：】n行，每行n個用空格隔開的數，表示馬到達該格子的最少步數，如果無法到達則用-1表示。2、馬的遍歷422----------+-----【樣例輸入：】4321303223-111214【樣例輸出：】０

const

dx:array[1..8]ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array[-1..maxn+2,-1..maxn+2]ofboolean;//加邊界，方便判斷是否出界

dist:array[1..maxn,1..maxn]ofinteger;//記錄最少步數

n,i,j,x0,y0:integer;procedureinit;//輸入vars:string;beginreadln(n,x0,y0);fillchar(can,sizeof(can),false);//初始化fori:=1tondobeginreadln(s);forj:=1tondocan[i,j]:=s[j]='-';end;end;procedurebfs;//廣度優先搜索

varq:array[1..maxn*m