上一節(jié)中我們學(xué)習(xí)了隊(duì)列，它是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。還有一種是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)它叫做棧。棧限定只能在一端進(jìn)行插入和刪除操作。比如說有一個小桶，小桶的直徑只能放一個小球，我們現(xiàn)在向小桶內(nèi)依次放入 2 號、1 號、3 號小球。假如你現(xiàn)在需要拿出 2 號小球，那就必須先將 3 號小球拿出，再拿出 1 號小球，最后才能將 2 號小球拿出來。在剛才取小球的過程中，我們最先放進(jìn)去的小球最后才能拿出來，而最后放進(jìn)去的小球卻可以最先拿出來。這就是后進(jìn)先出，也可以稱為先進(jìn)后出。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/5.1.png" alt="picture5.1" />

我們生活中還有很多這樣的例子，比如我們在吃桶裝薯片的時(shí)候，要想吃掉最后一片，就必須把前面的全部吃完（貌似現(xiàn)在的桶裝薯片為了減少分量，在桶里面增加了一個透明的抽屜）；再比如我們?yōu)g覽網(wǎng)頁時(shí)候需要退回到之前的某個網(wǎng)頁，我們需要一步步的點(diǎn)擊后退鍵。還有手-槍的彈夾，在裝子彈的時(shí)候，最后裝的一發(fā)子彈，是被第一個打出去的。棧的實(shí)現(xiàn)也很簡單，只需要一個一維數(shù)組和一個指向棧頂?shù)淖兞?top 就可以了。我們通過變量 top 來對棧進(jìn)行插入和刪除操作。

這種特殊的數(shù)據(jù)結(jié)構(gòu)棧究竟有哪些作用呢？我們來看一個例子?！皒yzyx”是一個回文字符串，所謂回文字符串就是指正讀反讀均相同的字符序列，如“席主席”、“記書記”、“aha”和“ahaha”均是回文，但“ahah”不是回文。通過棧這個數(shù)據(jù)結(jié)構(gòu)我們將很容易判斷一個字符串是否為回文。

首先我們需要讀取這行字符串，并求出這個字符串的長度。

char a[101]; //101是一個估算值，只需比待讀入的字符串長度大即可
int len;
gets(a);
len=strlen(a);

如果一個字符串是回文的話，那么它必須是中間對稱，我們需要求這個字符串的中點(diǎn)，即：

mid=len/2-1;

接下來就輪到棧出場了。

我們先將 mid 之前的部分的字符全部入棧。因?yàn)檫@里的棧是用來存儲字符的，所以這里用來實(shí)現(xiàn)棧的數(shù)組類型是字符數(shù)組即 char s[101]; 初始化棧很簡單，top=0;就可以了。入棧的操作是 top++;s[top]=x; （假設(shè)需要入棧的字符存儲暫存在字符變量 x 中）其實(shí)可以簡寫為 s[++top]=x;

現(xiàn)在我們就來將 mid 之前的字符依次全部入棧。這里循環(huán)要 0 開始，因?yàn)閯偛抛x取字符串使用了 gets()函數(shù)，讀取的第一個字符存儲在 s[0]中，隨后一個字符存儲在 s[len-1]中。


    for(i=0;i<=mid;i++)
    {
       s[++top]=a[i];
    }

接下來進(jìn)入判斷回文的關(guān)鍵步驟。將當(dāng)前棧中的字符依次出棧，看看是否能與 mid 之后的字符一一匹配，如果都能匹配則說明這個字符串是回文字符串，否則這個字符串就不是回文字符串。


    for(i=mid+1;i<=len-1;i++) //其實(shí)這里并不一定是mid+1，需要討論字符串長度的奇偶性
    {
    if (a[i]!=s[top])
       {
    break;
       }
       top--;
    }
    if(top==0)
       printf("YES");
    else
       printf("NO");

最后如果 top 的值為 0，就說明棧內(nèi)所有的字符都被一一匹配了，那么這個字符串就是回文字符串。完整的代碼如下。


    #include <stdio.h>
    #include <string.h>
    int main()
    {
    char a[101],s[101];
    int i,len,mid,next,top;

    gets(a); //讀入一行字符串
    len=strlen(a); //求字符串的長度
    mid=len/2-1; //求字符串的中點(diǎn)

    top=0;//棧的初始化
    //將mid前的字符依次入棧
    for(i=0;i<=mid;i++)
    s[++top]=a[i];

    //判斷字符串的長度的是奇數(shù)還是偶數(shù)，并找出需要進(jìn)行字符匹配的起始下標(biāo)
    if(len%2==0)
    next=mid+1;
    else
    next=mid+2;

    //開始匹配
    for(i=next;i<=len-1;i++)
    {
    if(a[i]!=s[top])
    break;
    top--;
    }

    //如果top的值為0，則說明棧內(nèi)的所有的字符都被一一匹配了
    if(top==0)
    printf("YES");
    else
    printf("NO");

    getchar();getchar();
    return 0;
    }

可以輸入以下數(shù)據(jù)進(jìn)行驗(yàn)證

ahaha

運(yùn)行結(jié)果是

YES

棧還可以用來進(jìn)行驗(yàn)證括號的匹配。比如輸入一行只包含“()[]{}”的字符串，形如“([{}()])”或者“{()[]{}}”請判斷是否可以正確匹配。顯然上面兩個例子都是可以正確匹配的?！?[)]”是不能匹配的。有興趣的同學(xué)可以自己動手來試一試。

堆棧最早由 Alan M. Turing（艾倫·圖靈）于 1946 年提出，當(dāng)時(shí)為了解決子程序的調(diào)用和返回。艾倫·圖靈這個大帥哥可是個大牛人，圖靈獎就是以他的名字命名的。如果你對他感興趣不妨去讀一讀他的傳記《艾倫圖靈傳：如謎的解謎者》。

【一周一算法】算法 5：解密回文——棧
 http://bbs.ahalei.com/thread-4515-1-1.html
(出處: 啊哈磊_編程從這里起步)

上一篇：算法 7：Dijkstra 最短路算法下一篇：算法 4：隊(duì)列——解密 QQ 號