前言
從數(shù)據(jù)結(jié)構(gòu)說起，面試了很多人，對于數(shù)據(jù)結(jié)構(gòu)總是說不清楚，有的說數(shù)組、鏈表，有的混進來堆、棧，甚至有的說不清隊列和堆的區(qū)別。這里寫一篇博客，總結(jié)下常見的數(shù)據(jù)結(jié)構(gòu)認(rèn)識誤區(qū)，就先從數(shù)組、鏈表開始吧。
區(qū)分
數(shù)組、鏈表是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之一，是一維的數(shù)據(jù)結(jié)構(gòu)，他們的區(qū)別是：
數(shù)組中元素地址連續(xù)的，鏈表中兩個元素地址不一定連續(xù)，而是由專門的一個指針指明該元素的后一個（前一個）元素的地址。
在此之上再衍生出來的其他一維數(shù)據(jù)結(jié)構(gòu)包括：隊列、棧、堆。他們都是滿足一定規(guī)則、或者說一定特性的數(shù)組、鏈表的拓展。這些拓展數(shù)據(jù)結(jié)構(gòu)，底層都可以使用數(shù)組或鏈表（基礎(chǔ)一維結(jié)構(gòu)）來實現(xiàn)。
PS：堆比較特殊，是指用數(shù)組實現(xiàn)的二叉樹。
堆區(qū)、棧區(qū)
對于操作系統(tǒng)為程序運行區(qū)分的堆區(qū)、棧區(qū)，也有很多的和堆、棧數(shù)據(jù)結(jié)構(gòu)搞混，這里介紹下什么是堆區(qū)、棧區(qū)。
堆區(qū)
由程序員調(diào)用malloc()函數(shù)來主動申請的，需使用free()函數(shù)來釋放內(nèi)存，若申請了堆區(qū)內(nèi)存，之后忘記釋放內(nèi)存，很容易造成內(nèi)存泄漏
棧區(qū)
棧區(qū)由編譯器自動分配釋放，存放函數(shù)的參數(shù)值、返回值和局部變量，在程序運行過程中實時分配和釋放，棧區(qū)由操作系統(tǒng)自動管理，無須手動管理。棧區(qū)是先進后出原則，即先進去的被堵在屋里的最里面，后進去的在門口，釋放的時候門口的先出去。
補充：
代碼區(qū)：存放程序的代碼，即CPU執(zhí)行的機器指令，并且是只讀的。
常量區(qū)：存放常量(程序在運行的期間不能夠被改變的量，例如: 10，字符串常量”abcde”， 數(shù)組的名字等)
靜態(tài)區(qū)（全局區(qū)）：靜態(tài)變量和全局變量的存儲區(qū)域是一起的，一旦靜態(tài)區(qū)的內(nèi)存被分配, 靜態(tài)區(qū)的內(nèi)存直到程序全部結(jié)束之后才會被釋放
小結(jié)
這期介紹了一些一維數(shù)據(jù)結(jié)構(gòu)，哪些是基礎(chǔ)存在的，哪些是衍生的。后續(xù)會將其中每一個拎出來講，側(cè)重點是實現(xiàn)方法和其中的優(yōu)化點。不要小看了數(shù)據(jù)結(jié)構(gòu)，很多巧妙的思想都是可以在這些數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)中找到。
參考
http://www.itdecent.cn/p/afbfc784238a
https://blog.csdn.net/u014470361/article/details/79297601
