通過之前的雙向佇列, 我們知道, 堆疊是一種只有尾部最後一個元素可以彈出, 插入也只能在尾端的元素. 因此在 STL 中, 它是作為 Container Adapter (容器配接器) 存在. 但是我們主要講的是資料結構, 而並不是 STL 的架構與剖析, 所以我們需要講解一下堆疊的具體結構

我們通過一張 SVG 圖像來看一下堆疊的結構 :

根據堆疊的性質, 通過圖像中的觀察, 我們可以得出, 每一次在堆疊中插入元素, 都只能在 last 位置插入; 每一次彈出元素, 也只能彈出 last - 1 對應位置的元素. 除此之外, 其它所有的元素在自己之後元素彈出之前, 都是不可以彈出的, 新來的元素也不能隨意選擇自己的位置. 除了這樣的限制之外, 甚至你都不可以訪問最後一個元素之前的任何一個元素

這樣嚴格的限制, 也就導致了 STL 選擇堆疊來做容器配接器的原因了. 並且我們還可以推斷出, Stack 中是不可能存在任何形式的疊代器的, 因為它只能訪問最後一個元素或者最後一個元素之後的位置, 疊代器存在的意義對於 Stack 來說並不太大

因此, 我們可以總結出 : 在堆疊中的元素, 最後進去的, 最先出來; 最先進去的, 最後出來

此時, 我們有一個疑問 : 如果我一不小心將堆疊的空間大小開的大了一些, 後面用不到的地方不是顯得非常浪費嗎?

沒錯, 當你用不到後面的位置, 但是後面的空間又非常大的時候, 這確實是一個棘手的問題

這個時候, 雙邊堆疊 (共享堆疊) 就可以解決這樣的問題

在 SVG 圖像中, 我們可以觀察到, 這個 Stack 前端是一個堆疊, 後端也是一個堆疊, 對空間的利用率比之前的堆疊要高不少

當然, 在空間足夠大的情況之下, 雙邊堆疊也可以演變為三邊、四邊甚至 n 邊, 這才是真正的共享堆疊. 當然, 我們這裡只是最多實現了雙邊而已

我們實現雙邊的方式也很簡單, 通過樣板特製化的方式

在 DataStructure 的堆疊中, 預設的堆疊和 STL 的堆疊一樣, 是一個容器配接器. 但是, 我們主要側重的是資料結構方面, 所以我們不僅僅需要一個容器配接器, 我們也需要實現一個真正的堆疊

因此, 我們同樣是通過樣板特製化的方式, 讓一個型別的指標充當一個堆疊的容器來實現. 這實際上是一個指標陣列

資料結構 Stack : GitHub 點擊直達

資料結構 Stack 使用說明 : GitHub 點擊直達