棧(stack)是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂(top)，相應地，表頭端稱為棧底(bottom)。棧的修改是按照後進先出的原則進行的。擴充棧操作是指對棧的基本操作（例如棧頂進行插入或刪除操作）進行擴充，使棧能進行一些其他操作，例如棧底也能進行插入或刪除操作。
基本介紹
- 中文名：擴充棧操作
- 外文名：extended stack operation
- 學科：計算機
- 定義：對棧的基本操作進行擴充
- 有關術語：棧
- 領域：數據結構
簡介,棧,緩衝區溢出,雙端棧,傳統雙端棧的存儲結構,雙端棧的動態存儲結構,套用,回溯,最長回文串匹配,
簡介
擴充棧操作是指對棧的基本操作（例如棧頂進行插入或刪除操作）進行擴充，使棧能進行一些其他操作。擴充棧操作需要對棧的結構進行修改，並對棧有關操作重新進行定義，例如雙端棧就是一種棧的變形，除了有棧一些基本操作以外，還擴充棧操作，使得棧的套用領域更加廣泛。
棧
亦稱堆疊。計算機記憶體中由程式指定的一個後進先出(LIFO)存儲區或CPU內部的一個LIFO暫存器組。前者稱軟棧，後者稱硬棧.軟棧的一端是固定的，另一端是浮動的，浮動的一端稱為棧頂.所有信息的存入和取出都只能在棧頂進行，而且是在堆疊指示字暫存器的配合下，按LIFO原則工作的。硬棧棧頂一端是固定的，壓入的數據項占據棧頂，棧中原有的數據項都依次向棧底方向移動；彈出數據時，最後進棧的數據項先被彈出，下面各級數據項依次向棧頂方向移動。軟棧和硬棧功能均相同，主要作為LIFO緩衝存儲器，用於中斷處理、子程式嵌套及暫存數據。在程式中斷時，堆疊(自動)保存程式計數器、狀態暫存器及工作暫存器的內容，並在中斷結束後把這些現場內容恢復到相應的暫存器中。
緩衝區溢出
緩衝區溢出是指當計算機向緩衝區內填充數據位數時超過了緩衝區本身的容量，溢出的數據覆蓋在合法數據上。理想的情況是：程式會檢查數據長度，而且並不允許輸入超過緩衝區長度的字元。但是絕大多數程式都會假設數據長度總是與所分配的儲存空間相匹配，這就為緩衝區溢出埋下隱患。作業系統所使用的緩衝區，又被稱為“堆疊”，在各個操作進程之間，指令會被臨時儲存在“堆疊”當中，“堆疊”也會出現緩衝區溢出。
雙端棧
棧是一種重要的數據結構， 堆疊技術被廣泛套用於編譯軟體和程式設計中。討論棧的結構特徵與操作實現特點，有著重要的意義。在棧的套用中經常會出現需要用到棧的共享技術， 在此共享技術中最常用的是兩棧的共享，即雙端棧。傳統的雙端棧總是事先開闢定量存儲空間M ，這樣造成了在程式運行過程中存儲空間的不足或浪費。 一般的做法是停止程式的執行，修改M 的值。若M 太大則會造成存儲空間的浪費，不能實現動態擴充的目的，也無法做到對閒置空間的自動回收。 以解決此問題為目的。
傳統雙端棧的存儲結構
在傳統的雙端棧中，兩個棧之間存在一種制約關係：兩個棧中的元素總數最大可以達到M ， 如果一個棧中的元素較多，那么另一個棧中的元素就較少，兩個棧中的元素總和超不過M 。 它主要利用了棧的 “棧底位置不變，而棧頂位置動態變化” 的特性。首先申請一個共享的一維數組空間S[M]，將兩個棧的棧底分別設在一維數組的兩端，分別是0 和M - 1。由於兩個棧頂動態變化，這樣可以形成互補，使得每個棧的可用的最大空間達到M 。傳統雙端棧的存儲結構定義如下：
typedef struct
{ ElemType Stack[M];
nt top[2];
}DqStack;
在雙端棧的套用中，如果數據元素有進有出，且存儲在雙端棧中的元素個數始終小於M-2 時，基本操作完全可行。但是在數據元素把存儲空間都占滿且又有元素需要入棧時，那么上述算法就無法解決了，只能出現 “溢出” ，數據元素入棧不成功。有人會認為可以在定義M 時將其放大到最大程度，但會發現M 越大，造成的空間浪費就越大；也有人會提出在空間不夠用時，停止程式的執行 再將M 放大一些，但是在一些大型系統開發中，系統一旦投入運行，就很難停止下來。
雙端棧的動態存儲結構
針對上面的問題，可以將ElemType 定義為指針類型*Stack，而非數組，這樣就不需要對雙端棧設定最大存儲空間M，而是給雙端棧設定初始值STACK_INIT_SIZE，通過動態記憶體分配函式malloc，給該指針分配存儲空間，且附設一個StackSize 來表示該空間的當前大小，若在程式執行中出現棧滿的情況，可以通過realloc 函式對該空間進行動態擴充，使其增加STACK_INCREMENT個單元。其新的類型定義如下：
# define STACK_INIT_SIZE 5
# define STACK_INCREMENT 5
# define STACK_FREESIZE 10
# define PERCENT 0.5
typedef struct
{ ElemType *Stack;
int top[2];
int StackSize;
}DqStack;
套用
回溯
回溯法（backtracking）是暴力搜尋法中的一種。對於某些計算問題而言，回溯法是一種可以找出所有（或一部分）解的一般性算法，尤其適用於約束滿足問題（在解決約束滿足問題時，我們逐步構造更多的候選解，並且在確定某一部分候選解不可能補全成正確解之後放棄繼續搜尋這個部分候選解本身及其可以拓展出的子候選解，轉而測試其他的部分候選解）。在經典的教科書中，八皇后問題展示了回溯法的用例。（八皇后問題是在標準西洋棋棋盤中尋找八個皇后的所有分布，使得沒有一個皇后能攻擊到另外一個。）回溯法採用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能的分步解答再次嘗試尋找問題的答案。回溯法通常用最簡單的遞歸方法來實現，在反覆重複上述的步驟後可能出現兩種情況：找到一個可能存在的正確的答案；在嘗試了所有可能的分步方法後宣告該問題沒有答案。在最壞的情況下，回溯法會導致一次複雜度為指數時間的計算。
最長回文串匹配
在計算機科學中，最長回文子串或最長對稱因子問題是在一個字元串中查找一個最長連續子串，這個子串必須是回文。例如“banana”最長回文子串是“anana”。最長回文子串並不能保證是唯一的，例如，在字元串“abracadabra”，沒有超過三的回文子串，但是有兩個回文字串長度都是三，是“ada”和“aca”。在一些套用中需要返回全部的最長回文子串(所有字串都是回文，並且不能擴展為更大的回文子串)而不是返回其中之一或是最大的回文子串的長度。
