第3章 棧與隊列

第3章棧與隊列BasicSortingAlgorithms2引言棧和隊列是軟件設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu);它們的邏輯結(jié)構(gòu)和線性表相同。其不同之處在于，棧和隊列的相關(guān)操作具有特殊性，它們只是線性表相關(guān)操作的一個子集。一般線性表上的插入、刪除操作不受限制，而棧和隊列上的插入、刪除操作均受某種特殊限制。因此，棧和隊列也稱作操作受限的線性表。3棧（stack）棧的概念棧是線性表的一個特例棧只能對線性表的固定一端進(jìn)行插入和刪除操作棧數(shù)據(jù)的主要特點是“后進(jìn)先出”（LastInFirstOut，LIFO）或“先進(jìn)后出”（FirstInLastOut，F(xiàn)ILO）的4棧（stack）棧的基本概念棧頂（Top）是棧中允許進(jìn)行數(shù)據(jù)插入和刪除的那一端。棧底（Bottom）是棧中無法進(jìn)行數(shù)據(jù)操作的那一端。棧上溢（Full）：在棧內(nèi)空間已存滿數(shù)據(jù)時，如果仍然希望能做壓棧動作，就會產(chǎn)生“上溢出”。棧下溢（Empty）：在棧內(nèi)空間已無數(shù)據(jù)時，如果仍然希望能做出棧動作，就會產(chǎn)生“下溢出”。棧頂壓棧an．．．a(chǎn)3a2a1出棧棧底5棧（stack）棧的操作——進(jìn)?；蛉霔＃≒ush）棧頂棧底ABCPush(A)Push(B)Push(C)6棧（stack）棧的操作——彈出或出棧（Pop）棧頂棧底ABCPop()Pop()Pop()7棧（stack）其它操作取數(shù)（peek）清除（clear）計數(shù)（count）Stack類的模擬實現(xiàn)（教材中的CStack）讀代碼，回答問題p_index變量的作用？CStack.Count是如何實現(xiàn)的？CStack的應(yīng)用——判定是否是“回文”在字符串中截取字符的兩種實現(xiàn)方法：substring和數(shù)組8棧（stack）C#中的Stack類System.Collections.StackStack構(gòu)造器方法StackmyStack=newStack();Stack<string>myStack=newStack<string>();string[]names=newstring[]{"Raymond","David","Mike"};StacknameStack=newStack(names);StackmyStack=newStack(25);主要操作Push（）Pop（）Peek（）Clear（）CopyTo（array，n）ToArray（）9實例簡單運算（P52-53）——問題？十進(jìn)制轉(zhuǎn)換（P55）修改程序可以進(jìn)行“十→二，十→八，十→十六”三種進(jìn)制轉(zhuǎn)換staticvoidMulBase(intn,intb){StackDigits=newStack();intremainder;do{remainder=n%b;if(remainder<=9)Digits.Push(remainder);elseDigits.Push((char)(remainder+55));//A的ASC碼是65n/=b;}while(n!=0);while(Digits.Count>0)Console.Write(Digits.Pop());Console.Read();}10隊列（Queue）隊列的定義隊列（Queue）是只允許在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表。它所有的插入均限定在表的一端進(jìn)行，該端稱為隊尾，所有的刪除則限定在表的另一端進(jìn)行，該端則稱為隊頭。入隊出隊a1a2…an隊頭隊尾11基本概念隊頭（Head）是隊列中允許數(shù)據(jù)刪除的那一端。隊尾（Tail）是隊列中允許數(shù)據(jù)插入的那一端。隊上溢（Full）：在隊內(nèi)空間存滿數(shù)據(jù)時，如果仍然希望做入隊動作，就會產(chǎn)生“上溢出”，這是一種空間不足的出錯狀態(tài)。隊下溢（Empty）：在隊內(nèi)空間已無數(shù)據(jù)時，如果仍然希望做出隊動作，就會產(chǎn)生“下溢出”，這是一種數(shù)據(jù)不足的出錯狀態(tài)。入隊出隊a1a2…an隊頭隊尾12基本操作入隊（Enqueue）隊頭隊尾ABCEnqueue(A)Enqueue(B)Enqueue(C)13基本操作出隊（Dequeue）隊頭隊尾ABCDequeue()14Queue類的實現(xiàn)（教材中的CQueue）讀代碼publicclassCQueue{privateArrayListpqueue;publicCQueue(){pqueue=newArrayList();}publicvoidEnQueue(objectitem){pqueue.Add(item);}publicvoidDeQueue(){pqueue.RemoveAt(0);}publicobjectPeek(){returnpqueue[0];}publicvoidClearQueue(){pqueue.Clear();}publicintCount(){returnpqueue.Count;}}15System.Collections.Queue的應(yīng)用實例化Queue<int>numbers=newQueue<int>();QueuemyQueue=newQueue(32,3);QueuemyQueue=newQueue(100);默認(rèn)初始容量是32。初始容量和增長倍數(shù)可以設(shè)定隊列的應(yīng)用舞池管理用隊列排序數(shù)據(jù)_基數(shù)排序優(yōu)先隊列基數(shù)排序，也叫桶排序第一步：根據(jù)個位數(shù)的數(shù)值，在走訪數(shù)值時將它們分配至編號0到9的桶子中。將這些桶子中的數(shù)值重新串接起來，形成新的數(shù)列。第二步：再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配。接下來將這些桶子中的數(shù)值重新串接起來舉例：9446851592353122進(jìn)桶、出桶重排16基數(shù)排序算法實現(xiàn)數(shù)據(jù)結(jié)構(gòu)10個隊列構(gòu)成的數(shù)組Queue[]que用于存放數(shù)據(jù)的整數(shù)數(shù)組int[]n取數(shù)取個位數(shù)n[x]%10取十位數(shù)n[x]/1017進(jìn)桶18staticvoidRSort(Queue[]que,int[]n,DigitTypedigit){intsnum;for(intx=0;x<=n.GetUpperBound(0);x++){if(digit==DigitType.ones)snum=n[x]%10;elsesnum=n[x]/10;que[snum].Enqueue(n[x]);}}19出桶staticvoidBuildArray(Queue[]que,int[]n){inty=0;for(intx=0;x>=9;x++)while(que[x].Count>0){n[y]=Int32.Parse(que[x].Dequeue().ToString());y++;}}基數(shù)排序算法改進(jìn)教材中的程序僅能對兩位數(shù)進(jìn)行基數(shù)排序，如何改進(jìn)程序可以能多位整數(shù)進(jìn)行基數(shù)排序教材中程序使用隊列，不用隊列這種數(shù)據(jù)結(jié)構(gòu)可以嗎？202122優(yōu)先隊列優(yōu)先級高的數(shù)據(jù)項先出隊列基本思想首先將隊列項寫入一個數(shù)組；然后遍歷數(shù)組找到最高優(yōu)先級的數(shù)據(jù)項；最后用這個標(biāo)記過的數(shù)組重建隊列，被標(biāo)記的項目被留下不用。23補充內(nèi)容——正則表達(dá)式正則表達(dá)式是指一個用來描述或者匹配一系列符合某個句法規(guī)則的字符串的單個字符串。在很多文本編輯器或其他工具里，正則表達(dá)式通常被用來檢索或替換那些符合某個模式的文本內(nèi)容。C#中的正則表達(dá)式包含在.NET基礎(chǔ)類庫的一個名稱空間下，這個名稱空間就是System.Text.RegularExpressions。該名稱空間包括8個類，1個枚舉，1個委托。Regex：編譯后的表達(dá)式的實例。24Regex類中還包含一些靜態(tài)的方法：Escape:對字符串中的regex中的轉(zhuǎn)義符進(jìn)行轉(zhuǎn)義；IsMatch:如果表達(dá)式在字符串中匹配，該方法返回一個布爾值；Match:返回Match的實例；Matches:返回一系列的Match的方法Replace:用替換字符串替換匹配的表達(dá)式Unescape:不對字符串中的轉(zhuǎn)義字符轉(zhuǎn)義。

25元字符描述$匹配行結(jié)束符。例如正則表達(dá)式weasel$能夠匹配字符串“He‘saweasel”的末尾，但是不能匹配字符串"Theyareabunchofweasels."^匹配一行的開始。例如正則表達(dá)式^Whenin能夠匹配字符串"Wheninthecourseofhumanevents"的開始，但是不能匹配"WhatandWheninthe"*匹配0或多個正好在它之前的那個字符。例如正則表達(dá)式.*意味著能夠匹配任意數(shù)量的任何字符。\這是引用符，用來將這里列出的這些元字符當(dāng)作普通的字符來進(jìn)行匹配。例如正則表達(dá)式\$被用來匹配美元符號，而不是行尾，類似的，正則表達(dá)式\.用來匹配點字符，而不是任何字符的通配符。\<\>匹配詞（word）的開始（\<）和結(jié)束（\>）。例如正則表達(dá)式\<the\>能夠匹配字符串"forthewise"中的"the"，但是不能匹配字符串"otherwise"中的"the"。注意：這個元字符不是所有的軟件都支持的。\(\)將\(和\)之間的表達(dá)式定義為“組”（group），并且將匹配這個表達(dá)式的字符保存到一個臨時區(qū)域（一個正則表達(dá)式中最多可以保存9個），它們可以用\1到\9的符號來引用。|將兩個匹配條件進(jìn)行邏輯“或”（Or）運算。例如正則表達(dá)式(him|her)匹配"itbelongstohim"和"itbelongstoher"，但是不能匹配"itbelongstothem."。注意：這個元字符不是所有的軟件都支持的。+匹配1或多個正好在它之前的那個字符。例如正則表達(dá)式9+匹配9、99、999等。注意：這個元字符不是所有的軟件都支持的。?匹配0或1個正好在它之前的那個字符。注意：這個元字符不是所有的軟件都支持的。\{i\}

\{i,j\}匹配指定數(shù)目的字符，這些字符是在它之前的表達(dá)式定義的。例如正則表達(dá)式A[0-9]\{3\}能夠匹配字符"A"后面跟著正好3個數(shù)字字符的串，例如A123、A348等，但是不匹配A1234。而正則表達(dá)式[0-9]\{4,6\}匹配連續(xù)的任意4個、5個或者