C# 數(shù)據(jù)結(jié)構(gòu) 棧 Stack

棧和隊(duì)列是非常重要的兩種數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列也是線性結(jié)構(gòu)，線性表、棧和隊(duì)列這三種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素和元素的邏輯關(guān)系也相同

差別在于：線性表的操作不受限制，棧和隊(duì)列操作受限制（遵循一定的原則），因此棧和隊(duì)列也稱為受限制的線性表。

棧的定義：操作在表的尾端進(jìn)行的線性表，棧頂：TOP，棧底：Bottom。棧中沒有數(shù)據(jù)：空棧Empty Stack

表示方法：S=（a1,a2,a3,a4……..an）a1為棧底的元素，an為棧頂?shù)脑?這N個(gè)數(shù)據(jù)按照先后順序插入到棧內(nèi)，找出棧內(nèi)數(shù)據(jù)則相反

遵循的原則（Last In First Out 即 LIFO) 或者 (First In Last Out 即 FILO)

現(xiàn)實(shí)生活中也有很多列子：洗盤子，用盤子

C#2.0 以下版本只提供了非泛型的 Stack 類，該類繼承了 ICollection、 IEnumerable 和 ICloneable 接口。 C#2.0 提供了泛型的

Stack<T>類，該類繼承 了 IEnumerable<T>、ICollection 和 IEnumerable 接口。

棧的存儲(chǔ)和實(shí)現(xiàn)

1.順序棧 ：用一塊連續(xù)存儲(chǔ)的空間來存儲(chǔ)棧中的元素，連續(xù)的空間就是數(shù)組表示了。

2.鏈棧：在線性鏈表的基礎(chǔ)上進(jìn)行操作的，也就說存儲(chǔ)結(jié)構(gòu)采用的是鏈表的形式而操作采用的是FILO方式。

生活中的實(shí)例

除了洗盤子是不是還有其他的使用方式呢？

1.數(shù)值轉(zhuǎn)換 是將非負(fù)數(shù)的十進(jìn)制轉(zhuǎn)換成其他進(jìn)制的數(shù)，一般的解決方法是輾轉(zhuǎn)相除法，例如：十進(jìn)制5142轉(zhuǎn)

成八進(jìn)制：

有圖我們可以看出 （5142）10=（12026）8

轉(zhuǎn)換思想：

1.判斷N不為0 N%8壓入到棧中

2.判斷N不為0 N%8壓入到棧中

最后N為0 停止，從而棧中的數(shù)據(jù)全部一個(gè)一個(gè)的POP得到八進(jìn)制數(shù)值。

2.程序設(shè)計(jì)中常用的問題：括號(hào)匹配問題，簡化起見，只有兩種括號(hào)匹配即：（）和[] 嵌套的順序是任意的

([]()) 匹配 [()[()][]] 匹配 [(]) 不匹配，加入有一堆這樣的匹配的符號(hào)怎么判斷呢？

思想：1.如果棧為空，則PUSH

2.如果括號(hào)和棧頂?shù)睦ㄌ?hào)匹配，則將棧頂?shù)睦ㄌ?hào)POP

3.如果括號(hào)和棧棧頂?shù)睦ㄌ?hào)不匹配，則將括號(hào)PUSH

4.最后結(jié)束時(shí)候判斷棧是否為空，為空則匹配，不為空則不匹配

3.常用的算術(shù)表達(dá)式…..可以自己思考一下……

未完待續(xù)………