白驹过隙，这篇文章距今已有一年以上的历史。技术发展日新月异，文中的观点或代码很可能过时或失效，请自行甄别：）

既然栈就是线性表,那么同样的也可以用链表的形式来表示,当然用链表表示的栈有一个学名,曰:链栈.

不过跟链表还是有一些不同,比如说头结点不用了,比如说,咱们得单独鼓捣一个结构体来保存栈顶的地址.好了,其它没什么,用代码说话吧

数据结构:

typedef struct Node{
    char Data;
    struct Node *next;
}*TopStack;

typedef struct {
    int Count;
    TopStack Top;
}TopPointer;

1.初始化:

BOOL InitializeStack(TopPointer *TP)
{
    TP=(TopPointer*)malloc(sizeof(TopPointer));//malloc the space to the TopPointer

    if(!TP)
        return false;

    TP->Count=0;
    TP->Top=NULL;

    return true;
}

2.入栈:

BOOL PushStack(TopPointer *TP,char TopValue)
{
    TopStack NewTop;

    NewTop=(TopStack)malloc(sizeof(TopStack));//malloc the new top value space
    if(!NewTop)
        return false;

    NewTop->Data=TopValue;//assign the value
    NewTop->next=TP->Top;

    TP->Top=NewTop;//point to the new top value address
    TP->Count++;

    return true;
}

3.出栈:

BOOL PopStack(TopPointer *TP,char *OldTopValue)
{
    TopStack OldTop;

    if(true==isStackEmpty(*TP))
        return false;

    OldTop=TP->Top;//get the old top address
    *OldTopValue=OldTop->Data;//get the old top value
    TP->Top=OldTop->next;//top pointer point to new top address
    TP->Count--;
    free(OldTop);//free the old top space

    return true;
}

4.查看栈顶数据:

BOOL GetTopValue(TopPointer TP,char *TopValue)
{
    if(true==isStackEmpty(TP))
        return false;

    *TopValue=(TP.Top)->Data;

    return true;
}

5.是否为空栈:

BOOL isStackEmpty(TopPointer TP)
{
    if(0==TP.Count)
        return true;
    return false;
}

6.栈的数据个数:

int StackLength(TopPointer TP)
{
    return TP.Count;
}

老规矩,写个程序跑一边,实践得真知不是?上代码:

#define true 1
#define false 0
#define error -1
#define BOOL int

#include<stdlib.h>
#include<stdio.h>

int main(void)
{
    TopPointer *TP;
    char PopValue;

    printf("Initialize the Stack...");
    if(false==InitializeStack(TP))
    {
        printf("Initialize Stack fail!The program will  be quited right now!\n");
        return -1;
    }
    printf("Initialize success!The length of the stack is %d\n",StackLength(*TP));
    printf("Push value 'a' to the stack!\n");
    if(false==PushStack(TP,'a'))
    {
        printf("Fail to push the value 'a'!");
    }
    printf("Success to push!Now the Length of the Stack is %d\n",StackLength(*TP));
    printf("Pop value...\n");
    if(false==PopStack(TP,&PopValue))
    {
        printf("Fail to pop the value!\n");
    }
    printf("Success to pop value '%c',the length of the stack is %d\n",PopValue,StackLength(*TP));

    return 0;
}

运行截图:

Capture.PNG

好了,说下栈的应用,最明显的递归了.话说当初学C的时候递归让我迷惑了好一会来着,尤其是老谭上面的那个碟子问题,还好,最后秒杀掉了.最著名的递归就是斐波那契数列.这里就不讲了.

第二个应用就是后缀表达式,神马是后缀表达式?那个,就是...就是伟大滴波兰逻辑学家Jan Lukasiewicz老人家发明的逆波兰表示法.尼玛!什么叫做逆波兰!那个...其实就是利用栈的先入后出原理来让计算机求四则运算的一种算法.用大话上的话讲就是"所有的符号都要在运算数字的后面出现".比如说书上的这个例子,咱们的运算"9+(3-1)3+10/2"用后缀表达式表示就是"9 3 1 - 3 + 10 2 / +",忘记说了,我们以前学的都是中缀表达式.

好了,怎么个转换法呢?中缀法转后缀法就是这么个规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号(乘除优先于加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止.额,看不懂?太刻板?好吧,用例子说话吧!还是那个"9+(3-1)3+10/2".看好了啊,咱们搞俩个栈,栈1放最后的最后的结果,栈2用来临时房运算符号.首先9进栈1,然后是+号进栈2,接着左括号)进栈2,接下来是3进栈1,然后-进栈2,然后数字1进栈1,接下来是右括号,咱们从小学就知道括号里面得先运算是吧,这里也一样,栈2里面的-符号进栈1,如果你跟我一起在纸上演算,那么现在可以看到栈1从栈底到栈顶依次是元素9 3 1 -,好了,咱们继续,号进栈2,然后3进栈1,接着+号进栈2,咳咳,注意了,按照规则"是右括号或优先级不高于栈顶符号(乘除优先于加减)则栈顶元素依次出栈并输出",号从栈2输出然后压入栈1,因为现在栈2是俩个+号,相同符号啊,注意相同符号的话就当做比现在的这个符号高级,所以原来的那个栈2的栈底元素+运算符号也从栈1出栈压入栈2,然后把咱们从我们的中缀表达式里面拿出来的这个+号压入栈2,现在栈1的元素从栈底到栈顶依次是9 3 1 - 3 +,栈2只有一个元素+,好了继续,接下来是10,进栈1,然后是/符号,进栈2,好了,到了最后一个元素2了,废话当然进栈1了,按照规则,当最后一个元素进栈1后,把栈2的元素分别出栈然后压入栈1,于是就是栈2的/和+分别压入栈1,好了,现在就得到我们的后缀表达式"9 3 1 - 3 * + 10 2 / +",灰常简单吧,嘿嘿嘿

再来看下后缀表达式的话计算机这厮是如何进行运算的呢?也先来规则吧:从左遍历表达式的每个数字和符号,遇到是数字就进栈,遇到事符号就将栈顶两个数字出栈,进行运算,一直到最终获得结果.还是用上面的例子吧,上面我们不是得出了后缀表达式吗,就用它吧,"9 3 1 - 3 + 10 2 / +",首先初始化一个栈,然后9进栈,3进栈,1进栈,移到-符号了,按照规则"遇到事符号就将栈顶两个数字出栈,进行运算",把1和3分别出栈,然后3-1的2,再把这个2进栈,然后3进栈,号来也,3和2出栈进行乘法运算,得6,6进栈,然后是+,好了,把栈底的9和栈顶的6出栈进行+法运算,的15,15进栈,然后10进栈,2进栈,到了/法了,2和10依次出来,皇上有请呢,除法后的5,5再进栈,哎呀,+号又来了,有完没完,栈顶的15和刚刚才进栈的5只好穿好衣服出来进行运算,这大晚上的不折腾人吗不是,好了,最后得20,额,咱们一看,咦,遍历到最后了,木数据了,好了,这个20就是这个表达式的值了.是不是很神奇,灰常滴神奇?不管你觉得神不神奇,反正我当初学会这招时对这个已经入土为安的Jan老祖宗佩服的五体投地,你说会不会也是在苹果树下思考如何鼓捣出后缀表达式然后苹果砸到了他就顿悟的呢,嘿嘿嘿

本来想用Jan老祖宗的后缀表达式写一个简易的计算器的,时候不早了,明天鼓捣吧

- 写于