漫畫(huà)算法（小灰的算法之旅）

漫畫(huà)算法小灰的算法之旅目錄\h第1章算法概述\h1.1算法和數(shù)據(jù)結(jié)構(gòu)\h1.1.1小灰和大黃\h1.1.2什么是算法\h1.1.3什么是數(shù)據(jù)結(jié)構(gòu)\h1.2時(shí)間復(fù)雜度\h1.2.1算法的好與壞\h1.2.2基本操作執(zhí)行次數(shù)\h1.2.3漸進(jìn)時(shí)間復(fù)雜度\h1.2.4時(shí)間復(fù)雜度的巨大差異\h1.3空間復(fù)雜度\h1.3.1什么是空間復(fù)雜度\h1.3.2空間復(fù)雜度的計(jì)算\h1.3.3時(shí)間與空間的取舍\h1.4小結(jié)\h第2章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)\h2.1什么是數(shù)組\h2.1.1初識(shí)數(shù)組\h2.1.2數(shù)組的基本操作\h2.1.3數(shù)組的優(yōu)勢(shì)和劣勢(shì)\h2.2什么是鏈表\h2.2.1“正規(guī)軍”和“地下黨”\h2.2.2鏈表的基本操作\h2.2.3數(shù)組VS鏈表\h2.3棧和隊(duì)列\(zhòng)h2.3.1物理結(jié)構(gòu)和邏輯結(jié)構(gòu)\h2.3.2什么是棧\h2.3.3棧的基本操作\h2.3.4什么是隊(duì)列\(zhòng)h2.3.5隊(duì)列的基本操作\h2.3.6棧和隊(duì)列的應(yīng)用\h22.4神奇的散列表\h2.4.1為什么需要散列表\h2.4.2哈希函數(shù)\h2.4.3散列表的讀寫(xiě)操作\h2.5小結(jié)\h第3章樹(shù)\h3.1樹(shù)和二叉樹(shù)\h3.1.1什么是樹(shù)\h3.1.2什么是二叉樹(shù)\h3.1.3二叉樹(shù)的應(yīng)用\h3.2二叉樹(shù)的遍歷\h3.2.1為什么要研究遍歷\h3.2.2深度優(yōu)先遍歷\h3.2.3廣度優(yōu)先遍歷\h3.3什么是二叉堆\h3.3.1初識(shí)二叉堆\h3.3.2二叉堆的自我調(diào)整\h3.3.3二叉堆的代碼實(shí)現(xiàn)\h3.4什么是優(yōu)先隊(duì)列\(zhòng)h3.4.1優(yōu)先隊(duì)列的特點(diǎn)\h3.4.2優(yōu)先隊(duì)列的實(shí)現(xiàn)\h3.5小結(jié)\h第4章排序算法\h4.1引言\h4.2什么是冒泡排序\h4.2.1初識(shí)冒泡排序\h4.2.2冒泡排序的優(yōu)化\h4.2.3雞尾酒排序\h4.3什么是快速排序\h4.3.1初識(shí)快速排序\h4.3.2基準(zhǔn)元素的選擇\h4.3.3元素的交換\h4.3.4單邊循環(huán)法\h4.3.5非遞歸實(shí)現(xiàn)\h4.4什么是堆排序\h4.4.1傳說(shuō)中的堆排序\h4.4.2堆排序的代碼實(shí)現(xiàn)\h4.5計(jì)數(shù)排序和桶排序\h4.5.1線(xiàn)性時(shí)間的排序\h4.5.2初識(shí)計(jì)數(shù)排序\h4.5.3計(jì)數(shù)排序的優(yōu)化\h4.5.4什么是桶排序\h4.6小結(jié)\h第5章面試中的算法\h5.1躊躇滿(mǎn)志的小灰\h5.2如何判斷鏈表有環(huán)\h5.2.1一場(chǎng)與鏈表相關(guān)的面試\h5.2.2解題思路\h5.2.3問(wèn)題擴(kuò)展\h5.3最小棧的實(shí)現(xiàn)\h5.3.1一場(chǎng)關(guān)于棧的面試\h5.3.2解題思路\h5.4如何求出最大公約數(shù)\h5.4.1一場(chǎng)求最大公約數(shù)的面試\h5.4.2解題思路\h5.5如何判斷一個(gè)數(shù)是否為2的整數(shù)次冪\h5.5.1一場(chǎng)很“2”的面試\h5.5.2解題思路\h5.6無(wú)序數(shù)組排序后的最大相鄰差\h5.6.1一道奇葩的面試題\h5.6.2解題思路\h5.7如何用棧實(shí)現(xiàn)隊(duì)列\(zhòng)h5.7.1又是一道關(guān)于棧的面試題\h5.7.2解題思路\h5.8尋找全排列的下一個(gè)數(shù)\h5.8.1一道關(guān)于數(shù)字的題目\h5.8.2解題思路\h5.9刪去k個(gè)數(shù)字后的最小值\h5.9.1又是一道關(guān)于數(shù)字的題目\h5.9.2解題思路\h5.10如何實(shí)現(xiàn)大整數(shù)相加\h5.10.1加法，你會(huì)不會(huì)\h5.10.2解題思路\h5.11如何求解金礦問(wèn)題\h5.11.1一個(gè)關(guān)于財(cái)富自由的問(wèn)題\h5.11.2解題思路\h5.12尋找缺失的整數(shù)\h5.12.1“五行”缺一個(gè)整數(shù)\h5.12.2問(wèn)題擴(kuò)展\h第6章算法的實(shí)際應(yīng)用\h6.1小灰上班的第1天\h6.2Bitmap的巧用\h6.2.1一個(gè)關(guān)于用戶(hù)標(biāo)簽的需求\h6.2.2用算法解決問(wèn)題\h6.3LRU算法的應(yīng)用\h6.3.1一個(gè)關(guān)于用戶(hù)信息的需求\h6.3.2用算法解決問(wèn)題\h6.4什么是A星尋路算法\h6.4.1一個(gè)關(guān)于迷宮尋路的需求\h6.4.2用算法解決問(wèn)題\h6.5如何實(shí)現(xiàn)紅包算法\h6.5.1一個(gè)關(guān)于錢(qián)的需求\h6.5.2用算法解決問(wèn)題\h6.6算法之路無(wú)止境第1章算法概述1.1算法和數(shù)據(jù)結(jié)構(gòu)1.1.1小灰和大黃在大四臨近畢業(yè)時(shí)，計(jì)算機(jī)專(zhuān)業(yè)的同學(xué)大都收到了滿(mǎn)意的offer，可是小灰卻還在著急上火。雖然他這幾天面試了很多家IT公司，可每次都被面試官“虐”得很慘很慘。就在心灰意冷之際，小灰忽然想到，他們系里有一位學(xué)霸名叫大黃，大黃不但技術(shù)很強(qiáng)，而且很樂(lè)意幫助同學(xué)。于是，小灰趕緊去找大黃，希望能夠得到一些指點(diǎn)。1.1.2什么是算法算法，對(duì)應(yīng)的英文單詞是algorithm，這是一個(gè)很古老的概念，最早來(lái)自數(shù)學(xué)領(lǐng)域。有一個(gè)關(guān)于算法的小故事，估計(jì)大家都有耳聞。在很久很久以前，曾經(jīng)有一個(gè)頑皮又聰明的“熊孩子”，天天在課堂上調(diào)皮搗蛋。終于有一天，老師忍無(wú)可忍，對(duì)“熊孩子”說(shuō)：臭小子，你又調(diào)皮??！今天罰你算加法，算出1+2+3+4+5+6+7……一直加到10000的結(jié)果，算不完不許回家！嘿嘿，我算就是了。老師以為，“熊孩子”會(huì)按部就班地一步一步計(jì)算，就像下面這樣。1+2=33+3=66+4=1010+5=15……這還不得算到明天天亮？夠這小子受的！老師心里幸災(zāi)樂(lè)禍地想著。誰(shuí)知僅僅幾分鐘后……老師，我算完了！結(jié)果是50005000，對(duì)不對(duì)？這、這、這……你小子怎么算得這么快？我讀書(shū)多，你騙不了我的！看著老師驚訝的表情，“熊孩子”微微一笑，講出了他的計(jì)算方法。首先把從1到10000這10000個(gè)數(shù)字兩兩分組相加，如下。1+10000=100012+9999=100013+9998=100014+9997=10001……一共有多少組這樣結(jié)果相同的和呢？有10000÷2即5000組。所以1到10000相加的總和可以這樣來(lái)計(jì)算：(1+10000)×10000÷2=50005000這個(gè)“熊孩子”就是后來(lái)著名的猶太數(shù)學(xué)家約翰·卡爾·弗里德里?！じ咚梗捎玫倪@種等差數(shù)列求和的方法，被稱(chēng)為高斯算法。（上文的故事情節(jié)與史實(shí)略有出入。）這是數(shù)學(xué)領(lǐng)域中算法的一個(gè)簡(jiǎn)單示例。在數(shù)學(xué)領(lǐng)域里，算法是用于解決某一類(lèi)問(wèn)題的公式和思想。而本書(shū)所涉及的算法，是計(jì)算機(jī)科學(xué)領(lǐng)域的算法，它的本質(zhì)是一系列程序指令，用于解決特定的運(yùn)算和邏輯問(wèn)題。從宏觀(guān)上來(lái)看，數(shù)學(xué)領(lǐng)域的算法和計(jì)算機(jī)領(lǐng)域的算法有很多相通之處。算法有簡(jiǎn)單的，也有復(fù)雜的。簡(jiǎn)單的算法，諸如給出一組整數(shù)，找出其中最大的數(shù)。復(fù)雜的算法，諸如在多種物品里選擇裝入背包的物品，使背包里的物品總價(jià)值最大，或找出從一個(gè)城市到另一個(gè)城市的最短路線(xiàn)。算法有高效的，也有拙劣的。剛才所講的從1加到10000的故事中，高斯所用的算法顯然是更加高效的算法，它利用等差數(shù)列的規(guī)律，四兩撥千斤，省時(shí)省力地求出了最終結(jié)果。而老師心中所想的算法，按部就班地一個(gè)數(shù)一個(gè)數(shù)進(jìn)行累加，則是一種低效、笨拙的算法。雖然這種算法也能得到最終結(jié)果，但是其計(jì)算過(guò)程要低效得多。在計(jì)算機(jī)領(lǐng)域，我們同樣會(huì)遇到各種高效和拙劣的算法。衡量算法好壞的重要標(biāo)準(zhǔn)有兩個(gè)。時(shí)間復(fù)雜度空間復(fù)雜度具體的概念會(huì)在本章進(jìn)行詳細(xì)講解。算法的應(yīng)用領(lǐng)域多種多樣。算法可以應(yīng)用在很多不同的領(lǐng)域中，其應(yīng)用場(chǎng)景更是多種多樣，例如下面這些。1.運(yùn)算有人或許會(huì)覺(jué)得，不就是數(shù)學(xué)運(yùn)算嗎？這還不簡(jiǎn)單？其實(shí)還真不簡(jiǎn)單。例如求出兩個(gè)數(shù)的最大公約數(shù)，要做到效率的極致，的確需要?jiǎng)右环X筋。再如計(jì)算兩個(gè)超大整數(shù)的和，按照正常方式來(lái)計(jì)算肯定會(huì)導(dǎo)致變量溢出。這又該如何求解呢？2.查找當(dāng)你使用谷歌、百度搜索某一個(gè)關(guān)鍵詞，或在數(shù)據(jù)庫(kù)中執(zhí)行某一條SQL語(yǔ)句時(shí)，你有沒(méi)有思考過(guò)數(shù)據(jù)和信息是如何被查出來(lái)的呢？3.排序排序算法是實(shí)現(xiàn)諸多復(fù)雜程序的基石。例如，當(dāng)瀏覽電商網(wǎng)站時(shí)，我們期望商品可以按價(jià)格從低到高進(jìn)行排序；當(dāng)瀏覽學(xué)生管理網(wǎng)站時(shí)，我們期望學(xué)生的資料可以按照學(xué)號(hào)的大小進(jìn)行排序。排序算法有很多種，它們的性能和優(yōu)缺點(diǎn)各不相同，這里面的學(xué)問(wèn)可大著呢。4.最優(yōu)決策有些算法可以幫助我們找到最優(yōu)的決策。例如在游戲中，可以讓AI角色找到迷宮的最佳路線(xiàn)，這涉及A星尋路算法。再如對(duì)于一個(gè)容量有限的背包來(lái)說(shuō)，如何決策才可以使放入的物品總價(jià)值最高，這涉及動(dòng)態(tài)規(guī)劃算法。5.面試（如果這條也算的話(huà)）凡是已走上工作崗位的程序員，在面試過(guò)程中多多少少都經(jīng)歷過(guò)算法問(wèn)題的考查。為什么面試官那么喜歡考查算法呢？考查算法問(wèn)題，一方面可以檢驗(yàn)程序員對(duì)計(jì)算機(jī)底層知識(shí)的了解，另一方面也可以衡量一下程序員的邏輯思維能力。1.1.3什么是數(shù)據(jù)結(jié)構(gòu)算法的概念我大致明白了，那數(shù)據(jù)結(jié)構(gòu)又是什么呢?數(shù)據(jù)結(jié)構(gòu)是算法的基石。如果把算法比喻成美麗靈動(dòng)的舞者，那么數(shù)據(jù)結(jié)構(gòu)就是舞者腳下廣闊而堅(jiān)實(shí)的舞臺(tái)。數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng)的英文單詞是datastructure，是數(shù)據(jù)的組織、管理和存儲(chǔ)格式，其使用目的是為了高效地訪(fǎng)問(wèn)和修改數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)都有哪些組成方式呢？1.線(xiàn)性結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)組、鏈表，以及由它們衍生出來(lái)的棧、隊(duì)列、哈希表。2.樹(shù)樹(shù)是相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其中比較有代表性的是二叉樹(shù)，由它又衍生出了二叉堆之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。3.圖圖是更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵趫D中會(huì)呈現(xiàn)出多對(duì)多的關(guān)聯(lián)關(guān)系。4.其他數(shù)據(jù)結(jié)構(gòu)除上述所列的幾種基本數(shù)據(jù)結(jié)構(gòu)以外，還有一些其他的千奇百怪的數(shù)據(jù)結(jié)構(gòu)。它們由基本數(shù)據(jù)結(jié)構(gòu)變形而來(lái)，用于解決某些特定問(wèn)題，如跳表、哈希鏈表、位圖等。有了數(shù)據(jù)結(jié)構(gòu)這個(gè)舞臺(tái)，算法才可以盡情舞蹈。在解決問(wèn)題時(shí)，不同的算法會(huì)選用不同的數(shù)據(jù)結(jié)構(gòu)。例如排序算法中的堆排序，利用的就是二叉堆這樣一種數(shù)據(jù)結(jié)構(gòu)；再如緩存淘汰算法LRU（LeastRecentlyUsed，最近最少使用），利用的就是特殊數(shù)據(jù)結(jié)構(gòu)哈希鏈表。關(guān)于算法在不同數(shù)據(jù)結(jié)構(gòu)上的操作過(guò)程，在后續(xù)的章節(jié)中我們會(huì)一一進(jìn)行學(xué)習(xí)。想不到算法和數(shù)據(jù)結(jié)構(gòu)包括這么多豐富多彩的內(nèi)容，大黃，我以后要好好跟你混！嘿嘿，我所掌握的也只是廣闊的算法海洋中的一個(gè)小水洼，讓我們一步一步來(lái)體驗(yàn)算法的無(wú)窮魅力吧！1.2時(shí)間復(fù)雜度1.2.1算法的好與壞時(shí)間復(fù)雜度和空間復(fù)雜度究竟是什么呢？首先，讓我們來(lái)想象一個(gè)場(chǎng)景。某一天，小灰和大黃同時(shí)加入了同一家公司。一天后，小灰和大黃交付了各自的代碼，兩人的代碼實(shí)現(xiàn)的功能差不多。大黃的代碼運(yùn)行一次要花100ms，占用內(nèi)存5MB。小灰的代碼運(yùn)行一次要花100s，占用內(nèi)存500MB。于是……在上述場(chǎng)景中，小灰雖然也按照老板的要求實(shí)現(xiàn)了功能，但他的代碼存在兩個(gè)很?chē)?yán)重的問(wèn)題。1.運(yùn)行時(shí)間長(zhǎng)運(yùn)行別人的代碼只要100ms，而運(yùn)行小灰的代碼則要100s，使用者肯定是無(wú)法忍受的。2.占用空間大別人的代碼只消耗5MB的內(nèi)存，而小灰的代碼卻要消耗500MB的內(nèi)存，這會(huì)給使用者造成很多麻煩。由此可見(jiàn)，運(yùn)行時(shí)間的長(zhǎng)短和占用內(nèi)存空間的大小，是衡量程序好壞的重要因素?？墒牵绻a都還沒(méi)有運(yùn)行，我怎么能預(yù)知代碼運(yùn)行所花的時(shí)間呢？由于受運(yùn)行環(huán)境和輸入規(guī)模的影響，代碼的絕對(duì)執(zhí)行時(shí)間是無(wú)法預(yù)估的。但我們卻可以預(yù)估代碼的基本操作執(zhí)行次數(shù)。1.2.2基本操作執(zhí)行次數(shù)關(guān)于代碼的基本操作執(zhí)行次數(shù)，下面用生活中的4個(gè)場(chǎng)景來(lái)進(jìn)行說(shuō)明。場(chǎng)景1給小灰1個(gè)長(zhǎng)度為10cm的面包，小灰每3分鐘吃掉1cm，那么吃掉整個(gè)面包需要多久？答案自然是3×10即30分鐘。如果面包的長(zhǎng)度是ncm呢？此時(shí)吃掉整個(gè)面包，需要3乘以n即3n分鐘。如果用一個(gè)函數(shù)來(lái)表達(dá)吃掉整個(gè)面包所需要的時(shí)間，可以記作T(n)=3n，n為面包的長(zhǎng)度。場(chǎng)景2給小灰1個(gè)長(zhǎng)度為16cm的面包，小灰每5分鐘吃掉面包剩余長(zhǎng)度的一半，即第5分鐘吃掉8cm，第10分鐘吃掉4cm，第15分鐘吃掉2cm……那么小灰把面包吃得只剩1cm，需要多久呢？這個(gè)問(wèn)題用數(shù)學(xué)方式表達(dá)就是，數(shù)字16不斷地除以2，那么除幾次以后的結(jié)果等于1？這里涉及數(shù)學(xué)中的對(duì)數(shù)，即以2為底16的對(duì)數(shù)log216。（注：本書(shū)下文中對(duì)數(shù)函數(shù)的底數(shù)全部省略。）因此，把面包吃得只剩下1cm，需要5×log16即20分鐘。如果面包的長(zhǎng)度是ncm呢？此時(shí)，需要5乘以logn即5logn分鐘，記作T(n)=5logn。場(chǎng)景3給小灰1個(gè)長(zhǎng)度為10cm的面包和1個(gè)雞腿，小灰每2分鐘吃掉1個(gè)雞腿。那么小灰吃掉整個(gè)雞腿需要多久呢？答案自然是2分鐘。因?yàn)檫@里只要求吃掉雞腿，和10cm的面包沒(méi)有關(guān)系。如果面包的長(zhǎng)度是ncm呢？無(wú)論面包多長(zhǎng)，吃掉雞腿的時(shí)間都是2分鐘，記作T(n)=2。場(chǎng)景4給小灰1個(gè)長(zhǎng)度為10cm的面包，小灰吃掉第1個(gè)1cm需要1分鐘時(shí)間，吃掉第2個(gè)1cm需要2分鐘時(shí)間，吃掉第3個(gè)1cm需要3分鐘時(shí)間……每吃1cm所花的時(shí)間就比吃上一個(gè)1cm多用1分鐘。那么小灰吃掉整個(gè)面包需要多久呢？答案是從1累加到10的總和，也就是55分鐘。如果面包的長(zhǎng)度是ncm呢？根據(jù)高斯算法，此時(shí)吃掉整個(gè)面包需要1+2+3+…+(n-1)+n即(1+n)×n/2分鐘，也就是0.5n2+0.5n分鐘，記作T(n)=0.5n2+0.5n。怎么除了吃還是吃??？這還不得撐死？上面所講的是吃東西所花費(fèi)的時(shí)間，這一思想同樣適用于對(duì)程序基本操作執(zhí)行次數(shù)的統(tǒng)計(jì)。設(shè)T(n)為程序基本操作執(zhí)行次數(shù)的函數(shù)（也可以認(rèn)為是程序的相對(duì)執(zhí)行時(shí)間函數(shù)），n為輸入規(guī)模，剛才的4個(gè)場(chǎng)景分別對(duì)應(yīng)了程序中最常見(jiàn)的4種執(zhí)行方式。場(chǎng)景1T(n)=3n，執(zhí)行次數(shù)是線(xiàn)性的。1.voideat1(intn){

2.for(inti=0;i<n;i++){;

3.System.out.println("等待1分鐘");

4.System.out.println("等待1分鐘");

5.System.out.println("吃1cm面包");

6.}

7.}

場(chǎng)景2T(n)=5logn，執(zhí)行次數(shù)是用對(duì)數(shù)計(jì)算的。1.voideat2(intn){

2.for(inti=n;i>1;i/=2){

3.System.out.println("等待1分鐘");

4.System.out.println("等待1分鐘");

5.System.out.println("等待1分鐘");

6.System.out.println("等待1分鐘");

7.System.out.println("吃一半面包");

8.}

9.}

場(chǎng)景3T(n)=2，執(zhí)行次數(shù)是常量。1.voideat3(intn){

2.System.out.println("等待1分鐘");

3.System.out.println("吃1個(gè)雞腿");

4.}

場(chǎng)景4T(n)=0.5n2+0.5n，執(zhí)行次數(shù)是用多項(xiàng)式計(jì)算的。1.voideat4(intn){

2.for(inti=0;i<n;i++){

3.for(intj=0;j<i;j++){

4.System.out.println("等待1分鐘");

5.}

6.System.out.println("吃1cm面包");

7.}

8.}

1.2.3漸進(jìn)時(shí)間復(fù)雜度有了基本操作執(zhí)行次數(shù)的函數(shù)T(n)，是否就可以分析和比較代碼的運(yùn)行時(shí)間了呢？還是有一定困難的。例如算法A的執(zhí)行次數(shù)是T(n)=100n，算法B的執(zhí)行次數(shù)是T(n)=5n2，這兩個(gè)到底誰(shuí)的運(yùn)行時(shí)間更長(zhǎng)一些呢？這就要看n的取值了。因此，為了解決時(shí)間分析的難題，有了漸進(jìn)時(shí)間復(fù)雜度（asymptotictimecomplexity）的概念，其官方定義如下。若存在函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱(chēng)為O(f(n))，O為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。因?yàn)闈u進(jìn)時(shí)間復(fù)雜度用大寫(xiě)O來(lái)表示，所以也被稱(chēng)為大O表示法。這個(gè)定義好晦澀呀，看不明白。直白地講，時(shí)間復(fù)雜度就是把程序的相對(duì)執(zhí)行時(shí)間函數(shù)T(n)簡(jiǎn)化為一個(gè)數(shù)量級(jí)，這個(gè)數(shù)量級(jí)可以是n、n2、n3等。如何推導(dǎo)出時(shí)間復(fù)雜度呢？有如下幾個(gè)原則。如果運(yùn)行時(shí)間是常數(shù)量級(jí)，則用常數(shù)1表示只保留時(shí)間函數(shù)中的最高階項(xiàng)如果最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù)讓我們回頭看看剛才的4個(gè)場(chǎng)景。場(chǎng)景1T(n)=3n，最高階項(xiàng)為3n，省去系數(shù)3，則轉(zhuǎn)化的時(shí)間復(fù)雜度為：T(n)=O(n)。場(chǎng)景2T(n)=5logn，最高階項(xiàng)為5logn，省去系數(shù)5，則轉(zhuǎn)化的時(shí)間復(fù)雜度為：T(n)=O(logn)。場(chǎng)景3T(n)=2，只有常數(shù)量級(jí)，則轉(zhuǎn)化的時(shí)間復(fù)雜度為：T(n)=O(1)。場(chǎng)景4T(n)=0.5n2+0.5n，最高階項(xiàng)為0.5n2，省去系數(shù)0.5，則轉(zhuǎn)化的時(shí)間復(fù)雜度為：T(n)=O(n2)。這4種時(shí)間復(fù)雜度究竟誰(shuí)的程度執(zhí)行用時(shí)更長(zhǎng)，誰(shuí)更節(jié)省時(shí)間呢？當(dāng)n的取值足夠大時(shí)，不難得出下面的結(jié)論：O(1)<O(logn)<O(n)<O(n2)在編程的世界中有各種各樣的算法，除了上述4個(gè)場(chǎng)景，還有許多不同形式的時(shí)間復(fù)雜度，例如：O(nlogn)、O(n3)、O(mn)、O(2n)、O(n!)今后當(dāng)我們遨游在代碼的海洋中時(shí)，會(huì)陸續(xù)遇到上述時(shí)間復(fù)雜度的算法。1.2.4時(shí)間復(fù)雜度的巨大差異大黃，我還有一個(gè)問(wèn)題，現(xiàn)在計(jì)算機(jī)硬件的性能越來(lái)越強(qiáng)了，我們?yōu)槭裁催€這么重視時(shí)間復(fù)雜度呢？問(wèn)得很好，讓我們用兩個(gè)算法來(lái)做一個(gè)對(duì)比，看一看高效算法和低效算法有多大的差距。舉例如下。算法A的執(zhí)行次數(shù)是T(n)=100n，時(shí)間復(fù)雜度是O(n)。算法B的執(zhí)行次數(shù)是T(n)=5n2，時(shí)間復(fù)雜度是O(n2)。算法A運(yùn)行在小灰家里的老舊電腦上，算法B運(yùn)行在某臺(tái)超級(jí)計(jì)算機(jī)上，超級(jí)計(jì)算機(jī)的運(yùn)行速度是老舊電腦的100倍。那么，隨著輸入規(guī)模n的增長(zhǎng)，兩種算法誰(shuí)運(yùn)行速度更快呢？從上面的表格可以看出，當(dāng)n的值很小時(shí)，算法A的運(yùn)行用時(shí)要遠(yuǎn)大于算法B；當(dāng)n的值在1000左右時(shí)，算法A和算法B的運(yùn)行時(shí)間已經(jīng)比較接近；隨著n的值越來(lái)越大，甚至達(dá)到十萬(wàn)、百萬(wàn)時(shí)，算法A的優(yōu)勢(shì)開(kāi)始顯現(xiàn)出來(lái)，算法B的運(yùn)行速度則越來(lái)越慢，差距越來(lái)越明顯。這就是不同時(shí)間復(fù)雜度帶來(lái)的差距。要想學(xué)好算法，就必須理解時(shí)間復(fù)雜度這個(gè)重要的基礎(chǔ)概念。有關(guān)時(shí)間復(fù)雜度的知識(shí)就介紹到這里，我們下一節(jié)再見(jiàn)！1.3空間復(fù)雜度1.3.1什么是空間復(fù)雜度在運(yùn)行一段程序時(shí)，我們不僅要執(zhí)行各種運(yùn)算指令，同時(shí)也會(huì)根據(jù)需要，存儲(chǔ)一些臨時(shí)的中間數(shù)據(jù)，以便后續(xù)指令可以更方便地繼續(xù)執(zhí)行。在什么情況下需要這些中間數(shù)據(jù)呢？讓我們來(lái)看看下面的例子。給出下圖所示的n個(gè)整數(shù)，其中有兩個(gè)整數(shù)是重復(fù)的，要求找出這兩個(gè)重復(fù)的整數(shù)。對(duì)于這個(gè)簡(jiǎn)單的需求，可以用很多種思路來(lái)解決，其中最樸素的方法就是雙重循環(huán)，具體如下。遍歷整個(gè)數(shù)列，每遍歷到一個(gè)新的整數(shù)就開(kāi)始回顧之前遍歷過(guò)的所有整數(shù)，看看這些整數(shù)里有沒(méi)有與之?dāng)?shù)值相同的。第1步，遍歷整數(shù)3，前面沒(méi)有數(shù)字，所以無(wú)須回顧比較。第2步，遍歷整數(shù)1，回顧前面的數(shù)字3，沒(méi)有發(fā)現(xiàn)重復(fù)數(shù)字。第3步，遍歷整數(shù)2，回顧前面的數(shù)字3、1，沒(méi)有發(fā)現(xiàn)重復(fù)數(shù)字。后續(xù)步驟類(lèi)似，一直遍歷到最后的整數(shù)2，發(fā)現(xiàn)和前面的整數(shù)2重復(fù)。雙重循環(huán)雖然可以得到最終結(jié)果，但它顯然并不是一個(gè)好的算法。它的時(shí)間復(fù)雜度是多少呢？根據(jù)上一節(jié)所學(xué)的方法，我們不難得出結(jié)論，這個(gè)算法的時(shí)間復(fù)雜度是O(n2)。那么，怎樣才能提高算法的效率呢？在這種情況下，我們就有必要利用一些中間數(shù)據(jù)了。如何利用中間數(shù)據(jù)呢？當(dāng)遍歷整個(gè)數(shù)列時(shí)，每遍歷一個(gè)整數(shù)，就把該整數(shù)存儲(chǔ)起來(lái)，就像放到字典中一樣。當(dāng)遍歷下一個(gè)整數(shù)時(shí)，不必再慢慢向前回溯比較，而直接去“字典”中查找，看看有沒(méi)有對(duì)應(yīng)的整數(shù)即可。假如已經(jīng)遍歷了數(shù)列的前7個(gè)整數(shù)，那么字典里存儲(chǔ)的信息如下?！白值洹弊髠?cè)的Key代表整數(shù)的值，“字典”右側(cè)的Value代表該整數(shù)出現(xiàn)的次數(shù)（也可以只記錄Key）。接下來(lái)，當(dāng)遍歷到最后一個(gè)整數(shù)2時(shí)，從“字典”中可以輕松找到2曾經(jīng)出現(xiàn)過(guò)，問(wèn)題也就迎刃而解了。由于讀寫(xiě)“字典”本身的時(shí)間復(fù)雜度是O(1)，所以整個(gè)算法的時(shí)間復(fù)雜度是O(n)，和最初的雙重循環(huán)相比，運(yùn)行效率大大提高了。而這個(gè)所謂的“字典”，是一種特殊的數(shù)據(jù)結(jié)構(gòu)，叫作散列表。這個(gè)數(shù)據(jù)結(jié)構(gòu)需要開(kāi)辟一定的內(nèi)存空間來(lái)存儲(chǔ)有用的數(shù)據(jù)信息。但是，內(nèi)存空間是有限的，在時(shí)間復(fù)雜度相同的情況下，算法占用的內(nèi)存空間自然是越小越好。如何描述一個(gè)算法占用的內(nèi)存空間的大小呢？這就用到了算法的另一個(gè)重要指標(biāo)——空間復(fù)雜度（spacecomplexity）。和時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，它同樣使用了大O表示法。程序占用空間大小的計(jì)算公式記作S(n)=O(f(n))，其中n為問(wèn)題的規(guī)模，f(n)為算法所占存儲(chǔ)空間的函數(shù)。1.3.2空間復(fù)雜度的計(jì)算基本的概念已經(jīng)明白了，那么，我們?nèi)绾蝸?lái)計(jì)算空間復(fù)雜度呢？具體情況要具體分析。和時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度也有幾種不同的增長(zhǎng)趨勢(shì)。常見(jiàn)的空間復(fù)雜度有下面幾種情形。1.常量空間當(dāng)算法的存儲(chǔ)空間大小固定，和輸入規(guī)模沒(méi)有直接的關(guān)系時(shí)，空間復(fù)雜度記作O(1)。例如下面這段程序：1.voidfun1(intn){

2.intvar=3;

3.…

4.}

2.線(xiàn)性空間當(dāng)算法分配的空間是一個(gè)線(xiàn)性的集合（如數(shù)組），并且集合大小和輸入規(guī)模n成正比時(shí)，空間復(fù)雜度記作O(n)。例如下面這段程序：1.voidfun2(intn){

2.int[]array=newint[n];

3.…

4.}

3.二維空間當(dāng)算法分配的空間是一個(gè)二維數(shù)組集合，并且集合的長(zhǎng)度和寬度都與輸入規(guī)模n成正比時(shí)，空間復(fù)雜度記作O(n2)。例如下面這段程序：1.voidfun3(intn){

2.int[][]matrix=newint[n][n];

3.…

4.}

4.遞歸空間遞歸是一個(gè)比較特殊的場(chǎng)景。雖然遞歸代碼中并沒(méi)有顯式地聲明變量或集合，但是計(jì)算機(jī)在執(zhí)行程序時(shí)，會(huì)專(zhuān)門(mén)分配一塊內(nèi)存，用來(lái)存儲(chǔ)“方法調(diào)用?！?。“方法調(diào)用?！卑ㄟM(jìn)棧和出棧兩個(gè)行為。當(dāng)進(jìn)入一個(gè)新方法時(shí)，執(zhí)行入棧操作，把調(diào)用的方法和參數(shù)信息壓入棧中。當(dāng)方法返回時(shí)，執(zhí)行出棧操作，把調(diào)用的方法和參數(shù)信息從棧中彈出。下面這段程序是一個(gè)標(biāo)準(zhǔn)的遞歸程序：1.voidfun4(intn){

2.if(n<=1){

3.return;

4.}

5.fun4(n-1);

6.…

7.}

假如初始傳入?yún)?shù)值n=5，那么方法fun4（參數(shù)n=5）的調(diào)用信息先入棧。接下來(lái)遞歸調(diào)用相同的方法，方法fun4（參數(shù)n=4）的調(diào)用信息入棧。以此類(lèi)推，遞歸越來(lái)越深，入棧的元素就越來(lái)越多。當(dāng)n=1時(shí)，達(dá)到遞歸結(jié)束條件，執(zhí)行return指令，方法出棧。最終，“方法調(diào)用?！钡娜吭貢?huì)一一出棧。由上面“方法調(diào)用?！钡某鋈霔＿^(guò)程可以看出，執(zhí)行遞歸操作所需要的內(nèi)存空間和遞歸的深度成正比。純粹的遞歸操作的空間復(fù)雜度也是線(xiàn)性的，如果遞歸的深度是n，那么空間復(fù)雜度就是O(n)。1.3.3時(shí)間與空間的取舍人們之所以花大力氣去評(píng)估算法的時(shí)間復(fù)雜度和空間復(fù)雜度，其根本原因是計(jì)算機(jī)的運(yùn)算速度和空間資源是有限的。就如一個(gè)大財(cái)主，基本不必為日?；ㄤN(xiāo)傷腦筋；而一個(gè)沒(méi)多少積蓄的普通人，則不得不為日?；ㄤN(xiāo)精打細(xì)算。對(duì)于計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)也是如此。雖然目前計(jì)算機(jī)的CPU處理速度不斷飆升，內(nèi)存和硬盤(pán)空間也越來(lái)越大，但是面對(duì)龐大而復(fù)雜的數(shù)據(jù)和業(yè)務(wù)，我們?nèi)匀灰蚣?xì)算，選擇最有效的利用方式。但是，正所謂魚(yú)和熊掌不可兼得。很多時(shí)候，我們不得不在時(shí)間復(fù)雜度和空間復(fù)雜度之間進(jìn)行取舍。在1.3.1小節(jié)尋找重復(fù)整數(shù)的例子中，雙重循環(huán)的時(shí)間復(fù)雜度是O(n2)，空間復(fù)雜度是O(1)，這屬于犧牲時(shí)間來(lái)?yè)Q取空間的情況。相反，字典法的空間復(fù)雜度是O(n)，時(shí)間復(fù)雜度是O(n)，這屬于犧牲空間來(lái)?yè)Q取時(shí)間的情況。在絕大多數(shù)時(shí)候，時(shí)間復(fù)雜度更為重要一些，我們寧可多分配一些內(nèi)存空間，也要提升程序的執(zhí)行速度。此外，說(shuō)起空間復(fù)雜度就離不開(kāi)數(shù)據(jù)結(jié)構(gòu)。在本章中，我們提及散列表、數(shù)組、二維數(shù)組這些常用的集合。如果大家對(duì)這些數(shù)據(jù)結(jié)構(gòu)不是很了解，可以仔細(xì)看看本書(shū)第2章關(guān)于基本數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，里面有詳細(xì)的介紹。關(guān)于空間復(fù)雜度的知識(shí)，我們就介紹到這里。時(shí)間復(fù)雜度和空間復(fù)雜度都是學(xué)好算法的重要前提，一定要牢牢掌握哦！1.4小結(jié)什么是算法在計(jì)算機(jī)領(lǐng)域里，算法是一系列程序指令，用于處理特定的運(yùn)算和邏輯問(wèn)題。衡量算法優(yōu)劣的主要標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和空間復(fù)雜度。什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織、管理和存儲(chǔ)格式，其使用目的是為了高效地訪(fǎng)問(wèn)和修改數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)包含數(shù)組、鏈表這樣的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，也包含樹(shù)、圖這樣的復(fù)雜數(shù)據(jù)結(jié)構(gòu)。什么是時(shí)間復(fù)雜度時(shí)間復(fù)雜度是對(duì)一個(gè)算法運(yùn)行時(shí)間長(zhǎng)短的量度，用大O表示，記作T(n)=O(f(n))。常見(jiàn)的時(shí)間復(fù)雜度按照從低到高的順序，包括O(1)、O(logn)、O(n)、O(nlogn)、O(n2)等。什么是空間復(fù)雜度空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，用大O表示，記作S(n)=O(f(n))。常見(jiàn)的空間復(fù)雜度按照從低到高的順序，包括O(1)、O(n)、O(n2)等。其中遞歸算法的空間復(fù)雜度和遞歸深度成正比。第2章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2.1什么是數(shù)組2.1.1初識(shí)數(shù)組這些特點(diǎn)是如何體現(xiàn)的呢？參加過(guò)軍訓(xùn)的讀者，一定都記得這樣的場(chǎng)景。在軍隊(duì)里，每一個(gè)士兵都有自己固定的位置、固定的編號(hào)。眾多士兵緊密團(tuán)結(jié)在一起，高效地執(zhí)行著一個(gè)個(gè)命令。大黃，咱們?yōu)槭裁匆f(shuō)這么多關(guān)于軍隊(duì)的事情呢？因?yàn)橛幸粋€(gè)數(shù)據(jù)結(jié)構(gòu)就像軍隊(duì)一樣整齊、有序，這個(gè)數(shù)據(jù)結(jié)構(gòu)叫作數(shù)組。什么是數(shù)組？數(shù)組對(duì)應(yīng)的英文是array，是有限個(gè)相同類(lèi)型的變量所組成的有序集合，數(shù)組中的每一個(gè)變量被稱(chēng)為元素。數(shù)組是最為簡(jiǎn)單、最為常用的數(shù)據(jù)結(jié)構(gòu)。以整型數(shù)組為例，數(shù)組的存儲(chǔ)形式如下圖所示。正如軍隊(duì)里的士兵存在編號(hào)一樣，數(shù)組中的每一個(gè)元素也有著自己的下標(biāo)，只不過(guò)這個(gè)下標(biāo)從0開(kāi)始，一直到數(shù)組長(zhǎng)度-1。數(shù)組的另一個(gè)特點(diǎn)，是在內(nèi)存中順序存儲(chǔ)，因此可以很好地實(shí)現(xiàn)邏輯上的順序表。數(shù)組在內(nèi)存中的順序存儲(chǔ)，具體是什么樣子呢？?jī)?nèi)存是由一個(gè)個(gè)連續(xù)的內(nèi)存單元組成的，每一個(gè)內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被其他數(shù)據(jù)占用了，有些是空閑的。數(shù)組中的每一個(gè)元素，都存儲(chǔ)在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲(chǔ)順序，也不能跳過(guò)某個(gè)存儲(chǔ)單元進(jìn)行存儲(chǔ)。在上圖中，橙色的格子代表空閑的存儲(chǔ)單元，灰色的格子代表已占用的存儲(chǔ)單元，而紅色的連續(xù)格子代表數(shù)組在內(nèi)存中的位置。不同類(lèi)型的數(shù)組，每個(gè)元素所占的字節(jié)個(gè)數(shù)也不同，本圖只是一個(gè)簡(jiǎn)單的示意圖。那么，我們?cè)鯓觼?lái)使用一個(gè)數(shù)組呢？數(shù)據(jù)結(jié)構(gòu)的操作無(wú)非是增、刪、改、查4種情況，下面讓我們來(lái)看一看數(shù)組的基本操作。2.1.2數(shù)組的基本操作1.讀取元素對(duì)于數(shù)組來(lái)說(shuō)，讀取元素是最簡(jiǎn)單的操作。由于數(shù)組在內(nèi)存中順序存儲(chǔ)，所以只要給出一個(gè)數(shù)組下標(biāo)，就可以讀取到對(duì)應(yīng)的數(shù)組元素。假設(shè)有一個(gè)名稱(chēng)為array的數(shù)組，我們要讀取數(shù)組下標(biāo)為3的元素，就寫(xiě)作array[3]；讀取數(shù)組下標(biāo)為5的元素，就寫(xiě)作array[5]。需要注意的是，輸入的下標(biāo)必須在數(shù)組的長(zhǎng)度范圍之內(nèi)，否則會(huì)出現(xiàn)數(shù)組越界。像這種根據(jù)下標(biāo)讀取元素的方式叫作隨機(jī)讀取。簡(jiǎn)單的代碼示例如下：1.int[]array=newint[]{3,1,2,5,4,9,7,2};

2.//輸出數(shù)組中下標(biāo)為3的元素

3.System.out.println(array[3]);

2.更新元素要把數(shù)組中某一個(gè)元素的值替換為一個(gè)新值，也是非常簡(jiǎn)單的操作。直接利用數(shù)組下標(biāo)，就可以把新值賦給該元素。簡(jiǎn)單的代碼示例如下：1.int[]array=newint[]{3,1,2,5,4,9,7,2};

2.//給數(shù)組下標(biāo)為5的元素賦值

3.array[5]=10;

4.//輸出數(shù)組中下標(biāo)為5的元素

5.System.out.println(array[5]);

小灰，咱們剛剛講過(guò)時(shí)間復(fù)雜度的概念，你說(shuō)說(shuō)數(shù)組讀取元素和更新元素的時(shí)間復(fù)雜度分別是多少？嘿嘿，這難不倒我。數(shù)組讀取元素和更新元素的時(shí)間復(fù)雜度都是O(1)。3.插入元素在介紹插入數(shù)組元素的操作之前，我們需要補(bǔ)充一個(gè)概念，那就是數(shù)組的實(shí)際元素?cái)?shù)量有可能小于數(shù)組的長(zhǎng)度，例如下面的情形。因此，插入數(shù)組元素的操作存在3種情況。尾部插入中間插入超范圍插入尾部插入，是最簡(jiǎn)單的情況，直接把插入的元素放在數(shù)組尾部的空閑位置即可，等同于更新元素的操作。中間插入，稍微復(fù)雜一些。由于數(shù)組的每一個(gè)元素都有其固定下標(biāo)，所以不得不首先把插入位置及后面的元素向后移動(dòng)，騰出地方，再把要插入的元素放到對(duì)應(yīng)的數(shù)組位置上。中間插入操作的完整實(shí)現(xiàn)代碼如下：1.privateint[]array;

2.privateintsize;

3.

4.publicMyArray(intcapacity){

5.this.array=newint[capacity];

6.size=0;

7.}

8.

9./**

10.*數(shù)組插入元素

11.*@paramelement插入的元素

12.*@paramindex插入的位置

13.*/

14.publicvoidinsert(intelement,intindex)throwsException{

15.//判斷訪(fǎng)問(wèn)下標(biāo)是否超出范圍

16.if(index<0||index>size){

17.thrownewIndexOutOfBoundsException("超出數(shù)組實(shí)際元素范圍！");

18.}

19.//從右向左循環(huán)，將元素逐個(gè)向右挪1位

20.for(inti=size-1;i>=index;i--){

21.array[i+1]=array[i];

22.}

23.//騰出的位置放入新元素

24.array[index]=element;

25.size++;

26.}

27.

28./**

29.*輸出數(shù)組

30.*/

31.publicvoidoutput(){

32.for(inti=0;i<size;i++){

33.System.out.println(array[i]);

34.}

35.}

36.

37.publicstaticvoidmain(String[]args)throwsException{

38.MyArraymyArray=newMyArray(10);

39.myArray.insert(3,0);

40.myArray.insert(7,1);

41.myArray.insert(9,2);

42.myArray.insert(5,3);

43.myArray.insert(6,1);

44.myArray.output();

45.}

代碼中的成員變量size是數(shù)組實(shí)際元素的數(shù)量。如果插入元素在數(shù)組尾部，傳入的下標(biāo)參數(shù)index等于size；如果插入元素在數(shù)組中間或頭部，則index小于size。如果傳入的下標(biāo)參數(shù)index大于size或小于0，則認(rèn)為是非法輸入，會(huì)直接拋出異常。可是，如果數(shù)組不斷插入新的元素，元素?cái)?shù)量超過(guò)了數(shù)組的最大長(zhǎng)度，數(shù)組豈不是要“撐爆”了？問(wèn)得很好，這就是接下來(lái)要講的情況——超范圍插入。超范圍插入，又是什么意思呢？假如現(xiàn)在有一個(gè)長(zhǎng)度為6的數(shù)組，已經(jīng)裝滿(mǎn)了元素，這時(shí)還想插入一個(gè)新元素。這就涉及數(shù)組的擴(kuò)容了?？墒菙?shù)組的長(zhǎng)度在創(chuàng)建時(shí)就已經(jīng)確定了，無(wú)法像孫悟空的金箍棒那樣隨意變長(zhǎng)或變短。這該如何是好呢？此時(shí)可以創(chuàng)建一個(gè)新數(shù)組，長(zhǎng)度是舊數(shù)組的2倍，再把舊數(shù)組中的元素統(tǒng)統(tǒng)復(fù)制過(guò)去，這樣就實(shí)現(xiàn)了數(shù)組的擴(kuò)容。如此一來(lái)，我們的插入元素方法也需要改寫(xiě)了，改寫(xiě)后的代碼如下：1.privateint[]array;

2.privateintsize;

3.

4.publicMyArray(intcapacity){

5.this.array=newint[capacity];

6.size=0;

7.}

8.

9./**

10.*數(shù)組插入元素

11.*@paramelement插入的元素

12.*@paramindex插入的位置

13.*/

14.publicvoidinsert(intelement,intindex)throwsException{

15.//判斷訪(fǎng)問(wèn)下標(biāo)是否超出范圍

16.if(index<0||index>size){

17.thrownewIndexOutOfBoundsException("超出數(shù)組實(shí)際元素范圍！");

18.}

19.//如果實(shí)際元素達(dá)到數(shù)組容量上限，則對(duì)數(shù)組進(jìn)行擴(kuò)容

20.if(size>=array.length){

21.resize();

22.}

23.//從右向左循環(huán)，將元素逐個(gè)向右挪1位

24.for(inti=size-1;i>=index;i--){

25.array[i+1]=array[i];

26.}

27.//騰出的位置放入新元素

28.array[index]=element;

29.size++;

30.}

31.

32./**

33.*數(shù)組擴(kuò)容

34.*/

35.publicvoidresize(){

36.int[]arrayNew=newint[array.length*2];

37.//從舊數(shù)組復(fù)制到新數(shù)組

38.System.arraycopy(array,0,arrayNew,0,array.length);

39.array=arrayNew;

40.}

41.

42./**

43.*輸出數(shù)組

44.*/

45.publicvoidoutput(){

46.for(inti=0;i<size;i++){

47.System.out.println(array[i]);

48.}

49.}

50.

51.publicstaticvoidmain(String[]args)throwsException{

52.MyArraymyArray=newMyArray(4);

53.myArray.insert(3,0);

54.myArray.insert(7,1);

55.myArray.insert(9,2);

56.myArray.insert(5,3);

57.myArray.insert(6,1);

58.myArray.output();

59.}

4.刪除元素?cái)?shù)組的刪除操作和插入操作的過(guò)程相反，如果刪除的元素位于數(shù)組中間，其后的元素都需要向前挪動(dòng)1位。由于不涉及擴(kuò)容問(wèn)題，所以刪除操作的代碼實(shí)現(xiàn)比插入操作要簡(jiǎn)單：1./**

2.*數(shù)組刪除元素

3.*@paramindex刪除的位置

4.*/

5.publicintdelete(intindex)throwsException{

6.//判斷訪(fǎng)問(wèn)下標(biāo)是否超出范圍

7.if(index<0||index>=size){

8.thrownewIndexOutOfBoundsException("超出數(shù)組實(shí)際元素范圍！");

9.}

10.intdeletedElement=array[index];

11.//從左向右循環(huán)，將元素逐個(gè)向左挪1位

12.for(inti=index;i<size-1;i++){

13.array[i]=array[i+1];

14.}

15.size--;

16.returndeletedElement;

17.}

小灰，我再考考你，數(shù)組的插入和刪除操作，時(shí)間復(fù)雜度分別是多少？先說(shuō)說(shuō)插入操作，數(shù)組擴(kuò)容的時(shí)間復(fù)雜度是O(n)，插入并移動(dòng)元素的時(shí)間復(fù)雜度也是O(n)，綜合起來(lái)插入操作的時(shí)間復(fù)雜度是O(n)。至于刪除操作，只涉及元素的移動(dòng)，時(shí)間復(fù)雜度也是O(n)。說(shuō)得沒(méi)錯(cuò)。對(duì)于刪除操作，其實(shí)還存在一種取巧的方式，前提是數(shù)組元素沒(méi)有順序要求。例如下圖所示，需要?jiǎng)h除的是數(shù)組中的元素2，可以把最后一個(gè)元素復(fù)制到元素2所在的位置，然后再刪除掉最后一個(gè)元素。這樣一來(lái)，無(wú)須進(jìn)行大量的元素移動(dòng)，時(shí)間復(fù)雜度降低為O(1)。當(dāng)然，這種方式只作參考，并不是刪除元素時(shí)主流的操作方式。2.1.3數(shù)組的優(yōu)勢(shì)和劣勢(shì)數(shù)組的基本知識(shí)我懂了，那么，使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)有什么優(yōu)勢(shì)和劣勢(shì)呢？數(shù)組擁有非常高效的隨機(jī)訪(fǎng)問(wèn)能力，只要給出下標(biāo)，就可以用常量時(shí)間找到對(duì)應(yīng)元素。有一種高效查找元素的算法叫作二分查找，就是利用了數(shù)組的這個(gè)優(yōu)勢(shì)。至于數(shù)組的劣勢(shì)，體現(xiàn)在插入和刪除元素方面。由于數(shù)組元素連續(xù)緊密地存儲(chǔ)在內(nèi)存中，插入、刪除元素都會(huì)導(dǎo)致大量元素被迫移動(dòng)，影響效率?？偟膩?lái)說(shuō)，數(shù)組所適合的是讀操作多、寫(xiě)操作少的場(chǎng)景，下一節(jié)我們要講解的鏈表則恰恰相反。好了，讓我們下一節(jié)再會(huì)！2.2什么是鏈表2.2.1“正規(guī)軍”和“地下黨”地下黨都是一些什么樣的人物呢？在影視作品中，我們可能都見(jiàn)到過(guò)地下工作者的經(jīng)典話(huà)語(yǔ)：“上級(jí)的姓名、住址，我知道，下級(jí)的姓名、住址，我也知道，但是這些都是我們黨的秘密，不能告訴你們！”地下黨借助這種單線(xiàn)聯(lián)絡(luò)的方式，靈活隱秘地傳遞著各種重要信息。在計(jì)算機(jī)科學(xué)領(lǐng)域里，有一種數(shù)據(jù)結(jié)構(gòu)也恰恰具備這樣的特征，這種數(shù)據(jù)結(jié)構(gòu)就是鏈表。鏈表是什么樣子的？為什么說(shuō)它像地下黨呢？讓我們來(lái)看一看單向鏈表的結(jié)構(gòu)。鏈表（linkedlist）是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)（node）所組成。單向鏈表的每一個(gè)節(jié)點(diǎn)又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針next。1.privatestaticclassNode{

2.intdata;

3.Nodenext;

4.}

鏈表的第1個(gè)節(jié)點(diǎn)被稱(chēng)為頭節(jié)點(diǎn)，最后1個(gè)節(jié)點(diǎn)被稱(chēng)為尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的next指針指向空。與數(shù)組按照下標(biāo)來(lái)隨機(jī)尋找元素不同，對(duì)于鏈表的其中一個(gè)節(jié)點(diǎn)A，我們只能根據(jù)節(jié)點(diǎn)A的next指針來(lái)找到該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)B，再根據(jù)節(jié)點(diǎn)B的next指針找到下一個(gè)節(jié)點(diǎn)C……這正如地下黨的聯(lián)絡(luò)方式，一級(jí)一級(jí)，單線(xiàn)傳遞。那么，通過(guò)鏈表的一個(gè)節(jié)點(diǎn)，如何能快速找到它的前一個(gè)節(jié)點(diǎn)呢？要想讓每個(gè)節(jié)點(diǎn)都能回溯到它的前置節(jié)點(diǎn)，我們可以使用雙向鏈表。什么是雙向鏈表？雙向鏈表比單向鏈表稍微復(fù)雜一些，它的每一個(gè)節(jié)點(diǎn)除了擁有data和next指針，還擁有指向前置節(jié)點(diǎn)的prev指針。接下來(lái)我們看一看鏈表的存儲(chǔ)方式。如果說(shuō)數(shù)組在內(nèi)存中的存儲(chǔ)方式是順序存儲(chǔ)，那么鏈表在內(nèi)存中的存儲(chǔ)方式則是隨機(jī)存儲(chǔ)。什么叫隨機(jī)存儲(chǔ)呢？上一節(jié)我們講解了數(shù)組的內(nèi)存分配方式，數(shù)組在內(nèi)存中占用了連續(xù)完整的存儲(chǔ)空間。而鏈表則采用了見(jiàn)縫插針的方式，鏈表的每一個(gè)節(jié)點(diǎn)分布在內(nèi)存的不同位置，依靠next指針關(guān)聯(lián)起來(lái)。這樣可以靈活有效地利用零散的碎片空間。讓我們看一看下面兩張圖，對(duì)比一下數(shù)組和鏈表在內(nèi)存中分配方式的不同。數(shù)組的內(nèi)存分配方式鏈表的內(nèi)存分配方式圖中的箭頭代表鏈表節(jié)點(diǎn)的next指針。那么，我們?cè)鯓觼?lái)使用一個(gè)鏈表呢？上一節(jié)剛剛講過(guò)數(shù)組的增、刪、改、查，這一次來(lái)看看鏈表的相關(guān)操作。2.2.2鏈表的基本操作1.查找節(jié)點(diǎn)在查找元素時(shí)，鏈表不像數(shù)組那樣可以通過(guò)下標(biāo)快速進(jìn)行定位，只能從頭節(jié)點(diǎn)開(kāi)始向后一個(gè)一個(gè)節(jié)點(diǎn)逐一查找。例如給出一個(gè)鏈表，需要查找從頭節(jié)點(diǎn)開(kāi)始的第3個(gè)節(jié)點(diǎn)。第1步，將查找的指針定位到頭節(jié)點(diǎn)。第2步，根據(jù)頭節(jié)點(diǎn)的next指針，定位到第2個(gè)節(jié)點(diǎn)。第3步，根據(jù)第2個(gè)節(jié)點(diǎn)的next指針，定位到第3個(gè)節(jié)點(diǎn)，查找完畢。小灰，你說(shuō)說(shuō)查找鏈表節(jié)點(diǎn)的時(shí)間復(fù)雜度是多少？鏈表中的數(shù)據(jù)只能按順序進(jìn)行訪(fǎng)問(wèn)，最壞的時(shí)間復(fù)雜度是O(n)。2.更新節(jié)點(diǎn)如果不考慮查找節(jié)點(diǎn)的過(guò)程，鏈表的更新過(guò)程會(huì)像數(shù)組那樣簡(jiǎn)單，直接把舊數(shù)據(jù)替換成新數(shù)據(jù)即可。3.插入節(jié)點(diǎn)與數(shù)組類(lèi)似，鏈表插入節(jié)點(diǎn)時(shí)，同樣分為3種情況。尾部插入頭部插入中間插入尾部插入，是最簡(jiǎn)單的情況，把最后一個(gè)節(jié)點(diǎn)的next指針指向新插入的節(jié)點(diǎn)即可。頭部插入，可以分成兩個(gè)步驟。第1步，把新節(jié)點(diǎn)的next指針指向原先的頭節(jié)點(diǎn)。第2步，把新節(jié)點(diǎn)變?yōu)殒湵淼念^節(jié)點(diǎn)。中間插入，同樣分為兩個(gè)步驟。第1步，新節(jié)點(diǎn)的next指針，指向插入位置的節(jié)點(diǎn)。第2步，插入位置前置節(jié)點(diǎn)的next指針，指向新節(jié)點(diǎn)。只要內(nèi)存空間允許，能夠插入鏈表的元素是無(wú)窮無(wú)盡的，不需要像數(shù)組那樣考慮擴(kuò)容的問(wèn)題。4.刪除元素鏈表的刪除操作同樣分為3種情況。尾部刪除頭部刪除中間刪除尾部刪除，是最簡(jiǎn)單的情況，把倒數(shù)第2個(gè)節(jié)點(diǎn)的next指針指向空即可。頭部刪除，也很簡(jiǎn)單，把鏈表的頭節(jié)點(diǎn)設(shè)為原先頭節(jié)點(diǎn)的next指針即可。中間刪除，同樣很簡(jiǎn)單，把要?jiǎng)h除節(jié)點(diǎn)的前置節(jié)點(diǎn)的next指針，指向要?jiǎng)h除元素的下一個(gè)節(jié)點(diǎn)即可。這里需要注意的是，許多高級(jí)語(yǔ)言，如Java，擁有自動(dòng)化的垃圾回收機(jī)制，所以我們不用刻意去釋放被刪除的節(jié)點(diǎn)，只要沒(méi)有外部引用指向它們，被刪除的節(jié)點(diǎn)會(huì)被自動(dòng)回收。小灰，我再考考你，鏈表的插入和刪除操作，時(shí)間復(fù)雜度分別是多少？如果不考慮插入、刪除操作之前查找元素的過(guò)程，只考慮純粹的插入和刪除操作，時(shí)間復(fù)雜度都是O(1)。很好，接下來(lái)看一看實(shí)現(xiàn)鏈表的完整代碼。1.//頭節(jié)點(diǎn)指針

2.privateNodehead;

3.//尾節(jié)點(diǎn)指針

4.privateNodelast;

5.//鏈表實(shí)際長(zhǎng)度

6.privateintsize;

7.

8./**

9.*鏈表插入元素

10.*@paramdata插入元素

11.*@paramindex插入位置

12.*/

13.publicvoidinsert(intdata,intindex)throwsException{

14.if(index<0||index>size){

15.thrownewIndexOutOfBoundsException("超出鏈表節(jié)點(diǎn)范圍！");

16.}

17.NodeinsertedNode=newNode(data);

18.if(size==0){

19.//空鏈表

20.head=insertedNode;

21.last=insertedNode;

22.}elseif(index==0){

23.//插入頭部

24.insertedNode.next=head;

25.head=insertedNode;

26.}elseif(size==index){

27.//插入尾部

28.last.next=insertedNode;

29.last=insertedNode;

30.}else{

31.//插入中間

32.NodeprevNode=get(index-1);

33.insertedNode.next=prevNode.next;

34.prevNode.next=insertedNode;

35.}

36.size++;

37.}

38.

39./**

40.*鏈表刪除元素

41.*@paramindex刪除的位置

42.*/

43.publicNoderemove(intindex)throwsException{

44.if(index<0||index>=size){

45.thrownewIndexOutOfBoundsException("超出鏈表節(jié)點(diǎn)范圍！");

46.}

47.NoderemovedNode=null;

48.if(index==0){

49.//刪除頭節(jié)點(diǎn)

50.removedNode=head;

51.head=head.next;

52.}elseif(index==size-1){

53.//刪除尾節(jié)點(diǎn)

54.NodeprevNode=get(index-1);

55.removedNode=prevNode.next;

56.prevNode.next=null;

57.last=prevNode;

58.}else{

59.//刪除中間節(jié)點(diǎn)

60.NodeprevNode=get(index-1);

61.NodenextNode=prevNode.next.next;

62.removedNode=prevNode.next;

63.prevNode.next=nextNode;

64.}

65.size--;

66.returnremovedNode;

67.}

68.

69./**

70.*鏈表查找元素

71.*@paramindex查找的位置

72.*/

73.publicNodeget(intindex)throwsException{

74.if(index<0||index>=size){

75.thrownewIndexOutOfBoundsException("超出鏈表節(jié)點(diǎn)范圍！");

76.}

77.Nodetemp=head;

78.for(inti=0;i<index;i++){

79.temp=temp.next;

80.}

81.returntemp;

82.}

83.

84./**

85.*輸出鏈表

86.*/

87.publicvoidoutput(){

88.Nodetemp=head;

89.while(temp!=null){

90.System.out.println(temp.data);

91.temp=temp.next;

92.}

93.}

94.

95./**

96.*鏈表節(jié)點(diǎn)

97.*/

98.privatestaticclassNode{

99.intdata;

100.Nodenext;

101.Node(intdata){

102.this.data=data;

103.}

104.}

105.

106.publicstaticvoidmain(String[]args)throwsException{

107.MyLinkedListmyLinkedList=newMyLinkedList();

108.myLinkedList.insert(3,0);

109.myLinkedList.insert(7,1);

110.myLinkedList.insert(9,2);

111.myLinkedList.insert(5,3);

112.myLinkedList.insert(6,1);

113.myLinkedList.remove(0);

114.myLinkedList.output();

115.}

以上是對(duì)單鏈表相關(guān)操作的代碼實(shí)現(xiàn)。為了尾部插入的方便，代碼中額外增加了指向鏈表尾節(jié)點(diǎn)的指針last。2.2.3數(shù)組VS鏈表鏈表的基本知識(shí)我懂了。數(shù)組和鏈表都屬于線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，用哪一個(gè)更好呢？數(shù)據(jù)結(jié)構(gòu)沒(méi)有絕對(duì)的好與壞，數(shù)組和鏈表各有千秋。下面我總結(jié)了數(shù)組和鏈表相關(guān)操作的性能，我們來(lái)對(duì)比一下。從表格可以看出，數(shù)組的優(yōu)勢(shì)在于能夠快速定位元素，對(duì)于讀操作多、寫(xiě)操作少的場(chǎng)景來(lái)說(shuō)，用數(shù)組更合適一些。相反地，鏈表的優(yōu)勢(shì)在于能夠靈活地進(jìn)行插入和刪除操作，如果需要在尾部頻繁插入、刪除元素，用鏈表更合適一些。關(guān)于鏈表的知識(shí)我們就介紹到這里，咱們下一節(jié)再見(jiàn)！2.3棧和隊(duì)列2.3.1物理結(jié)構(gòu)和邏輯結(jié)構(gòu)什么是數(shù)據(jù)存儲(chǔ)的物理結(jié)構(gòu)呢？如果把數(shù)據(jù)結(jié)構(gòu)比作活生生的人，那么物理結(jié)構(gòu)就是人的血肉和骨骼，看得見(jiàn)，摸得著，實(shí)實(shí)在在。例如我們剛剛學(xué)過(guò)的數(shù)組和鏈表，都是內(nèi)存中實(shí)實(shí)在在的存儲(chǔ)結(jié)構(gòu)。而在物質(zhì)的人體之上，還存在著人的思想和精神，它們看不見(jiàn)、摸不著?？催^(guò)電影《阿凡達(dá)》嗎？男主角的思想意識(shí)從一個(gè)瘦弱殘疾的人類(lèi)身上被移植到一個(gè)高大威猛的藍(lán)皮膚外星人身上，雖然承載思想意識(shí)的肉身改變了，但是人格卻是唯一的。如果把物質(zhì)層面的人體比作數(shù)據(jù)存儲(chǔ)的物理結(jié)構(gòu)，那么精神層面的人格則是數(shù)據(jù)存儲(chǔ)的邏輯結(jié)構(gòu)。邏輯結(jié)構(gòu)是抽象的概念，它依賴(lài)于物理結(jié)構(gòu)而存在。下面我們來(lái)講解兩個(gè)常用數(shù)據(jù)結(jié)構(gòu)：棧和隊(duì)列。這兩者都屬于邏輯結(jié)構(gòu)，它們的物理實(shí)現(xiàn)既可以利用數(shù)組，也可以利用鏈表來(lái)完成。在后面的章節(jié)中，我們會(huì)學(xué)習(xí)到二叉樹(shù)，這也是一種邏輯結(jié)構(gòu)。同樣地，二叉樹(shù)也可以依托于物理上的數(shù)組或鏈表來(lái)實(shí)現(xiàn)。2.3.2什么是棧要弄明白什么是棧，我們需要先舉一個(gè)生活中的例子。假如有一個(gè)又細(xì)又長(zhǎng)的圓筒，圓筒一端封閉，另一端開(kāi)口。往圓筒里放入乒乓球，先放入的靠近圓筒底部，后放入的靠近圓筒入口。那么，要想取出這些乒乓球，則只能按照和放入順序相反的順序來(lái)取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球優(yōu)先取出。棧（stack）是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，它就像一個(gè)上圖所示的放入乒乓球的圓筒容器，棧中的元素只能先入后出（FirstInLastOut，簡(jiǎn)稱(chēng)FILO）。最早進(jìn)入的元素存放的位置叫作棧底（bottom），最后進(jìn)入的元素存放的位置叫作棧頂（top）。棧這種數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)。棧的數(shù)組實(shí)現(xiàn)如下。棧的鏈表實(shí)現(xiàn)如下。那么，棧可以進(jìn)行哪些操作呢？棧的最基本操作是入棧和出棧，下面讓我們來(lái)看一看。2.3.3棧的基本操作1.入棧入棧操作（push）就是把新元素放入棧中，只允許從棧頂一側(cè)放入元素，新元素的位置將會(huì)成為新的棧頂。這里我們以數(shù)組實(shí)現(xiàn)為例。2.出棧出棧操作（pop）就是把元素從棧中彈出，只有棧頂元素才允許出棧，出棧元素的前一個(gè)元素將會(huì)成為新的棧頂。這里我們以數(shù)組實(shí)現(xiàn)為例。由于棧操作的代碼實(shí)現(xiàn)比較簡(jiǎn)單，這里就不再展示代碼了，有興趣的讀者可以自己寫(xiě)寫(xiě)看。小灰，你說(shuō)說(shuō)，入棧和出棧操作，時(shí)間復(fù)雜度分別是多少？入棧和出棧只會(huì)影響到最后一個(gè)元素，不涉及其他元素的整體移動(dòng)，所以無(wú)論是以數(shù)組還是以鏈表實(shí)現(xiàn)，入棧、出棧的時(shí)間復(fù)雜度都是O(1)。2.3.4什么是隊(duì)列要弄明白什么是隊(duì)列，我們同樣可以用一個(gè)生活中的例子來(lái)說(shuō)明。假如公路上有一條單行隧道，所有通過(guò)隧道的車(chē)輛只允許從隧道入口駛?cè)?，從隧道出口駛出，不允許逆行。因此，要想讓車(chē)輛駛出隧道，只能按照它們駛?cè)胨淼赖捻樞?，先駛?cè)氲能?chē)輛先駛出，后駛?cè)氲能?chē)輛后駛出，任何車(chē)輛都無(wú)法跳過(guò)它前面的車(chē)輛提前駛出。隊(duì)列（queue）是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，它的特征和行駛車(chē)輛的單行隧道很相似。不同于棧的先入后出，隊(duì)列中的元素只能先入先出（FirstInFirstOut，簡(jiǎn)稱(chēng)FIFO）。隊(duì)列的出口端叫作隊(duì)頭（front），隊(duì)列的入口端叫作隊(duì)尾（rear）。與棧類(lèi)似，隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)時(shí)，為了入隊(duì)操作的方便，把隊(duì)尾位置規(guī)定為最后入隊(duì)元素的下一個(gè)位置。隊(duì)列的數(shù)組實(shí)現(xiàn)如下。隊(duì)列的鏈表實(shí)現(xiàn)如下。那么，隊(duì)列可以進(jìn)行哪些操作呢？和棧操作相對(duì)應(yīng)，隊(duì)列的最基本操作是入隊(duì)和出隊(duì)。2.3.5隊(duì)列的基本操作對(duì)于鏈表實(shí)現(xiàn)方式，隊(duì)列的入隊(duì)、出隊(duì)操作和棧是大同小異的。但對(duì)于數(shù)組實(shí)現(xiàn)方式來(lái)說(shuō)，隊(duì)列的入隊(duì)和出隊(duì)操作有了一些有趣的變化。怎么有趣呢？我們后面會(huì)看到。1.入隊(duì)入隊(duì)（enqueue）就是把新元素放入隊(duì)列中，只允許在隊(duì)尾的位置放入元素，新元素的下一個(gè)位置將會(huì)成為新的隊(duì)尾。2.出隊(duì)出隊(duì)操作（dequeue）就是把元素移出隊(duì)列，只允許在隊(duì)頭一側(cè)移出元素，出隊(duì)元素的后一個(gè)元素將會(huì)成為新的隊(duì)頭。如果像這樣不斷出隊(duì)，隊(duì)頭左邊的空間失去作用，那隊(duì)列的容量豈不是越來(lái)越小了？例如像下面這樣。問(wèn)得很好，這正是我后面要講的。用數(shù)組實(shí)現(xiàn)的隊(duì)列可以采用循環(huán)隊(duì)列的方式來(lái)維持隊(duì)列容量的恒定。循環(huán)隊(duì)列是什么意思呢？讓我們看看下面的例子。假設(shè)一個(gè)隊(duì)列經(jīng)過(guò)反復(fù)的入隊(duì)和出隊(duì)操作，還剩下2個(gè)元素，在“物理”上分布于數(shù)組的末尾位置。這時(shí)又有一個(gè)新元素將要入隊(duì)。在數(shù)組不做擴(kuò)容的前提下，如何讓新元素入隊(duì)并確定新的隊(duì)尾位置呢？我們可以利用已出隊(duì)元素留下的空間，讓隊(duì)尾指針重新指回?cái)?shù)組的首位。這樣一來(lái)，整個(gè)隊(duì)列的元素就“循環(huán)”起來(lái)了。在物理存儲(chǔ)上，隊(duì)尾的位置也可以在隊(duì)頭之前。當(dāng)再有元素入隊(duì)時(shí)，將其放入數(shù)組的首位，隊(duì)尾指針繼續(xù)后移即可。一直到（隊(duì)尾下標(biāo)+1）%數(shù)組長(zhǎng)度=隊(duì)頭下標(biāo)時(shí)，代表此隊(duì)列真的已經(jīng)滿(mǎn)了。需要注意的是，隊(duì)尾指針指向的位置永遠(yuǎn)空出1位，所以隊(duì)列最大容量比數(shù)組長(zhǎng)度小1。這就是所謂的循環(huán)隊(duì)列，下面讓我們來(lái)看一看它的代碼實(shí)現(xiàn)。1.privateint[]array;

2.privateintfront;

3.privateintrear;

4.

5.publicMyQueue(intcapacity){

6.this.array=newint[capacity];

7.}

8.

9./**

10.*入隊(duì)

11.*@paramelement入隊(duì)的元素

12.*/

13.publicvoidenQueue(intelement)throwsException{

14.if((rear+1)%array.length==front){

15.thrownewException("隊(duì)列已滿(mǎn)！");

16.}

17.array[rear]=element;

18.rear=(rear+1)%array.length;

19.}

20.

21./**

22.*出隊(duì)

23.*/

24.publicintdeQueue()throwsException{

25.if(rear==front){

26.thrownewException("隊(duì)列已空！");

27.}

28.intdeQueueElement=array[front];

29.front=(front+1)%array.length;

30.returndeQueueElement;

31.}

32.

33./**

34.*輸出隊(duì)列

35.*/

36.publicvoidoutput(){

37.for(inti=front;i!=rear;i=(i+1)%array.length){

38.System.out.println(array[i]);

39.}

40.}

41.

42.publicstaticvoidmain(String[]args)throwsException{

43.MyQueuemyQueue=newMyQueue(6);

44.myQueue.enQueue(3);

45.myQueue.enQueue(5);

46.myQueue.enQueue(6);

47.myQueue.enQueue(8);

48.myQueue.enQueue(1);

49.myQueue.deQueue();

50.myQueue.deQueue();

51.myQueue.deQueue();

52.myQueue.enQueue(2);

53.myQueue.enQueue(4);

54.myQueue.enQueue(9);

55.myQueue.output();

56.}

循環(huán)隊(duì)列不但充分利用了數(shù)組的空間，還避免了數(shù)組元素整體移動(dòng)的麻煩，還真是有點(diǎn)意思呢！至于入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度，也同樣是O(1)吧？說(shuō)得完全正確！下面我們來(lái)看一看棧和隊(duì)列都可以應(yīng)用在哪些地方。2.3.6棧和隊(duì)列的應(yīng)用1.棧的應(yīng)用棧的輸出順序和輸入順序相反，所以棧通常用于對(duì)“歷史”的回溯，也就是逆流而上追溯“歷史”。例如實(shí)現(xiàn)遞歸的邏輯，就可以用棧來(lái)代替，因?yàn)闂？梢曰厮莘椒ǖ恼{(diào)用鏈。棧還有一個(gè)著名的應(yīng)用場(chǎng)景是面包屑導(dǎo)航，使用戶(hù)在瀏覽頁(yè)面時(shí)可以輕松地回溯到上一級(jí)或更上一級(jí)頁(yè)面。2.隊(duì)列的應(yīng)用隊(duì)列的輸出順序和輸入順序相同，所以隊(duì)列通常用于對(duì)“歷史”的回放，也就是按照“歷史”順序，把“歷史”重演一遍。例如在多線(xiàn)程中，爭(zhēng)奪公平鎖的等待隊(duì)列，就是按照訪(fǎng)問(wèn)順序來(lái)決定線(xiàn)程在隊(duì)列中的次序的。再如網(wǎng)絡(luò)爬蟲(chóng)實(shí)現(xiàn)網(wǎng)站抓取時(shí)，也是把待抓取的網(wǎng)站URL存入隊(duì)列中，再按照存入隊(duì)列的順序來(lái)依次抓取和解析的。3.雙端隊(duì)列那么，有沒(méi)有辦法把棧和隊(duì)列的特點(diǎn)結(jié)合起來(lái)，既可以先入先出，也可以先入后出呢？還真有，這種數(shù)據(jù)結(jié)構(gòu)叫作雙端隊(duì)列（deque）。雙端隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，可以說(shuō)綜合了棧和隊(duì)列的優(yōu)點(diǎn)，對(duì)雙端隊(duì)列來(lái)說(shuō)，從隊(duì)頭一端可以入隊(duì)或出隊(duì)，從隊(duì)尾一端也可以入隊(duì)或出隊(duì)。有關(guān)雙端隊(duì)列的細(xì)節(jié)，感興趣的讀者可以查閱資料做更多的了解。4.優(yōu)先隊(duì)列還有一種隊(duì)列，它遵循的不是先入先出，而是誰(shuí)的優(yōu)先級(jí)最高，誰(shuí)先出隊(duì)。這種隊(duì)列叫作優(yōu)先隊(duì)列。優(yōu)先隊(duì)列已經(jīng)不屬于線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的范疇了，它是基于二叉堆來(lái)實(shí)現(xiàn)的。關(guān)于優(yōu)先隊(duì)列的原理和使用情況，我們會(huì)在下一章進(jìn)行詳細(xì)介紹。好了，關(guān)于棧和隊(duì)列的知識(shí)我們就介紹到這里，下一節(jié)再見(jiàn)！22.4神奇的散列表2.4.1為什么需要散列表說(shuō)起學(xué)習(xí)英語(yǔ)，小灰上學(xué)時(shí)可沒(méi)有那么豐富的學(xué)習(xí)資源和工具。當(dāng)時(shí)有一款很流行的電子詞典，小伙伴們遇到不會(huì)的單詞，只要輸入到小小的電子詞典里，就可以查出它的中文含義。當(dāng)時(shí)的英語(yǔ)老師強(qiáng)烈反對(duì)使用這樣的工具，因?yàn)殡娮釉~典查出來(lái)的中文資料太有限，而傳統(tǒng)的紙質(zhì)詞典可以查到單詞的多種含義、詞性、例句等。但是，同學(xué)們還是傾向于使用電子詞典。因?yàn)殡娮釉~典實(shí)在太方便了，只要輸入要查的單詞，一瞬間就可以得到結(jié)果，而不需要像紙質(zhì)詞典那樣煩瑣地進(jìn)行人工查找。在我們的程序世界里，往往也需要在內(nèi)存中存放這樣一個(gè)“詞典”，方便我們進(jìn)行高效的查詢(xún)和統(tǒng)計(jì)。例如開(kāi)發(fā)一個(gè)學(xué)生管理系統(tǒng)，需要有通過(guò)輸入學(xué)號(hào)快速查出對(duì)應(yīng)學(xué)生的姓名的功能。這里不必每次都去查詢(xún)數(shù)據(jù)庫(kù)，而可以在內(nèi)存中建立一個(gè)緩存表，這樣做可以提高查詢(xún)效率。再如我們需要統(tǒng)計(jì)一本英文書(shū)里某些單詞出現(xiàn)的頻率，就需要遍歷整本書(shū)的內(nèi)容，把這些單詞出現(xiàn)的次數(shù)記錄在內(nèi)存中。因?yàn)檫@些需求，一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)誕生了，這個(gè)數(shù)據(jù)結(jié)構(gòu)叫作散列表。散列表也叫作哈希表（hashtable），這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。只要給出一個(gè)Key，就可以高效查找到它所匹配的Value，時(shí)間復(fù)雜度接近于O(1)。那么，散列表是如何根據(jù)Key來(lái)快速找到它所匹配的Value呢？這就是我下面要講的散列表的基本原理。2.4.2哈希函數(shù)小灰，在咱們之前學(xué)過(guò)的幾個(gè)數(shù)據(jù)結(jié)構(gòu)中，誰(shuí)的查詢(xún)效率最高？當(dāng)然是數(shù)組嘍，數(shù)組可以根據(jù)下標(biāo)，進(jìn)行元素的隨機(jī)訪(fǎng)問(wèn)。說(shuō)得沒(méi)錯(cuò)，散列表在本質(zhì)上也是一個(gè)數(shù)組。可是數(shù)組只能根據(jù)下標(biāo)，像a[0]、a[1]、a[2]、a[3]、a[4]這樣來(lái)訪(fǎng)問(wèn)，而散列表的Key則是以字符串類(lèi)型為主的。例如以學(xué)生的學(xué)號(hào)作為Key，輸入002123，查詢(xún)到李四；或者以單詞為Key，輸入by，查詢(xún)到數(shù)字46……所以我們需要一個(gè)“中轉(zhuǎn)站”，通過(guò)某種方式，把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換。這個(gè)中轉(zhuǎn)站就叫作哈希函數(shù)。這個(gè)所謂的哈希函數(shù)是怎么實(shí)現(xiàn)的呢？在不同的語(yǔ)言中，哈希函數(shù)的實(shí)現(xiàn)方式是不一樣的。這里以Java的常用集合HashMap為例，來(lái)看一看哈希函數(shù)在Java中的實(shí)現(xiàn)。在Java及大多數(shù)面向?qū)ο蟮恼Z(yǔ)言中，每一個(gè)對(duì)象都有屬于自己的hashcode，這個(gè)hashcode是區(qū)分不同對(duì)象的重要標(biāo)識(shí)。無(wú)論對(duì)象自身的類(lèi)型是什么，它們的hashcode都是一個(gè)整型變量。既然都是整型變量，想要轉(zhuǎn)化成數(shù)組的下標(biāo)也就不難實(shí)現(xiàn)了。最簡(jiǎn)單的轉(zhuǎn)化方式是什么呢？是按照數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算。index=HashCode(Key)%Array.length實(shí)際上，JDK（JavaDevelopmentKit，Java語(yǔ)言的軟件開(kāi)發(fā)工具包）中的哈希函數(shù)并沒(méi)有直接采用取模運(yùn)算，而是利用了位運(yùn)算的方式來(lái)優(yōu)化性能。不過(guò)在這里可以姑且簡(jiǎn)單理解成取模操作。通過(guò)哈希函數(shù)，我們可以把字符串或其他類(lèi)型的Key，轉(zhuǎn)化成數(shù)組的下標(biāo)index。如給出一個(gè)長(zhǎng)度為8的數(shù)組，則當(dāng)key=001121時(shí)，index=HashCode("001121")%Array.length=1420036703%8=7而當(dāng)key=this時(shí)，index=HashCode("t