棧和隊(duì)列

棧和隊(duì)列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu),它們都來自線性表數(shù)據(jù)結(jié)構(gòu)纽窟,都是“操作受限”的線性表填具。

棧(Stack):是限制在表的一端進(jìn)行插入和刪除操作的線性表。又稱為后進(jìn)先出LIFO (Last In First Out)或先進(jìn)后出FILO (First In Last Out)線性表艰额。

棧頂(Top):允許進(jìn)行插入澄港、刪除操作的一端,又稱為表尾柄沮。用棧頂指針(top)來指示棧頂元素回梧。

棧底(Bottom):是固定端,又稱為表頭祖搓。

空棧:當(dāng)表中沒有元素時(shí)稱為空棧狱意。

設(shè)棧S=(a1,a2拯欧,…an)详囤,則a1稱為棧底元素,an為棧頂元素镐作,如圖1-1所示藏姐。
  棧中元素按a1,a2该贾,…an的次序進(jìn)棧羔杨,退棧的第一個(gè)元素應(yīng)為棧頂元素。即棧的修改是按后進(jìn)先出的原則進(jìn)行的杨蛋。

圖1-1.png

棧的順序存儲(chǔ)表示

棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧兜材,和線性表相類似,用一維數(shù)組來存儲(chǔ)棧六荒。根據(jù)數(shù)組是否可以根據(jù)需要增大护姆,又可分為靜態(tài)順序棧和動(dòng)態(tài)順序棧。

棧的動(dòng)態(tài)順序存儲(chǔ)表示

采用動(dòng)態(tài)一維數(shù)組來存儲(chǔ)棧掏击。所謂動(dòng)態(tài)卵皂,指的是棧的大小可以根據(jù)需要增加。

  • 用bottom表示棧底指針砚亭,棧底固定不變的灯变;棧頂則隨著進(jìn)棧和退棧操作而變化殴玛。用top(稱為棧頂指針)指示當(dāng)前棧頂位置。
  • 用top=bottom作為椞砘觯空的標(biāo)記滚粟,每次top指向棧頂數(shù)組中的下一個(gè)存儲(chǔ)位置。
  • 結(jié)點(diǎn)進(jìn)棧:首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)刃泌,然后執(zhí)行top加1凡壤,使top指向棧頂?shù)南乱粋€(gè)存儲(chǔ)位置;

棧的靜態(tài)順序存儲(chǔ)表示

采用靜態(tài)一維數(shù)組來存儲(chǔ)棧。

  • 棧底固定不變的耙替;棧頂則隨著進(jìn)棧和退棧操作而變化亚侠,用一個(gè)整型變量top(稱為棧頂指針)來指示當(dāng)前棧頂位置。
  • 用top=0表示椝咨龋空的初始狀態(tài)硝烂,每次top指向棧頂在數(shù)組中的存儲(chǔ)位置。
  • 結(jié)點(diǎn)進(jìn)棧:首先執(zhí)行top加1铜幽,使top指向新的棧頂位置滞谢,然后將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)。

當(dāng)棧滿時(shí)做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出除抛,簡(jiǎn)稱“上溢”狮杨。上溢是一種出錯(cuò)狀態(tài),應(yīng)設(shè)法避免到忽。
  當(dāng)椇探矗空時(shí)做退棧運(yùn)算也將產(chǎn)生溢出,簡(jiǎn)稱“下溢”绘趋。下溢則可能是正巢眨現(xiàn)象,因?yàn)闂T谑褂脮r(shí)陷遮,其初態(tài)或終態(tài)都是空棧滓走,所以下溢常用來作為控制轉(zhuǎn)移的條件。

棧的鏈?zhǔn)酱鎯?chǔ)表示

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧帽馋,是運(yùn)算受限的單鏈表搅方。其插入和刪除操作只能在表頭位置上進(jìn)行。因此绽族,鏈棧沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)姨涡,棧頂指針top就是鏈表的頭指針。圖1-2是棧的鏈?zhǔn)酱鎯?chǔ)表示形式吧慢。

圖1-2.png

隊(duì)列

隊(duì)列(Queue):也是運(yùn)算受限的線性表涛漂。是一種先進(jìn)先出(First In First Out ,簡(jiǎn)稱FIFO)的線性表。只允許在表的一端進(jìn)行插入匈仗,而在另一端進(jìn)行刪除瓢剿。
隊(duì)首(front) :允許進(jìn)行刪除的一端稱為隊(duì)首。
隊(duì)尾(rear) :允許進(jìn)行插入的一端稱為隊(duì)尾悠轩。
  例如:排隊(duì)購(gòu)物间狂。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列火架。

Paste_Image.png

隊(duì)列的順序表示

利用一組連續(xù)的存儲(chǔ)單元(一維數(shù)組) 依次存放從隊(duì)首到隊(duì)尾的各個(gè)元素鉴象,稱為順序隊(duì)列。
   對(duì)于隊(duì)列何鸡,和順序棧相類似炼列,也有動(dòng)態(tài)和靜態(tài)之分

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列,它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表音比。
  需要兩類不同的結(jié)點(diǎn):數(shù)據(jù)元素結(jié)點(diǎn),隊(duì)列的隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)氢惋,如圖1-3所示洞翩。

圖1-3.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市焰望,隨后出現(xiàn)的幾起案子骚亿,更是在濱河造成了極大的恐慌,老刑警劉巖熊赖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件来屠,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡震鹉,警方通過查閱死者的電腦和手機(jī)俱笛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來传趾,“玉大人迎膜,你說我怎么就攤上這事〗迹” “怎么了磕仅?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)簸呈。 經(jīng)常有香客問我榕订,道長(zhǎng),這世上最難降的妖魔是什么蜕便? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任劫恒,我火速辦了婚禮,結(jié)果婚禮上轿腺,老公的妹妹穿的比我還像新娘兼贸。我一直安慰自己段直,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布溶诞。 她就那樣靜靜地躺著鸯檬,像睡著了一般。 火紅的嫁衣襯著肌膚如雪螺垢。 梳的紋絲不亂的頭發(fā)上喧务,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音枉圃,去河邊找鬼妻熊。 笑死贞岭,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播婉刀,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼唉窃!你這毒婦竟也來了窟蓝?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤篮绿,失蹤者是張志新(化名)和其女友劉穎孵延,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體亲配,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡尘应,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了吼虎。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片犬钢。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖思灰,靈堂內(nèi)的尸體忽然破棺而出娜饵,到底是詐尸還是另有隱情,我是刑警寧澤官辈,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布箱舞,位于F島的核電站,受9級(jí)特大地震影響拳亿,放射性物質(zhì)發(fā)生泄漏晴股。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一肺魁、第九天 我趴在偏房一處隱蔽的房頂上張望电湘。 院中可真熱鬧,春花似錦、人聲如沸寂呛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)贷痪。三九已至幻妓,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間劫拢,已是汗流浹背肉津。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留舱沧,地道東北人妹沙。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像熟吏,于是被迫代替她去往敵國(guó)和親距糖。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容