一個數據結構中棧的應用
時間：2018-08-16 來源：未知
在linux的shell命令下不知道有沒有同學使用dc命令。這是一個算數命令。相信同學們對這種算式都比較熟悉：（1 + 2）* 3結果等于9 dc命令也是一種算式表達——壓棧式算術運算。
當輸入dc命令后我們像上圖那樣輸入，特點是遇到運算符對前面兩個數進行運算，然后再講結果返回。那么上面的算式就是1和2相加后結果返回，然后遇到乘法后，再將1和2相加的結果與3相乘，摁p輸出結果。
仔細看一下這個過程，是不是和壓棧很像。過程大體是這樣的：
1.數字依次進棧
2.遇到運算符將處于棧頂的兩個元素出棧，根據運算符計算出結果，然后再將結果壓棧。
3.依次進行指導“p”將結果輸出。
當然，這其中還有很多細節，比如后棧里只有單個數字，則自己和自己運算等。我們這里先不考慮這些。只是實現上面簡單的功能，做個拋磚引玉，供同學們繼續思考深化。
我們看一下下面的程序：
int main(int argc,const char *argv[])
{
int i = 0,x,y;
sqstack * sq;
if((sq = stack_create()) == NULL)
return -1;
while(*argv[i] != 'p')
{
if(*argv[i] <= '9' && *argv[i] >= '0')
push(sq,(*argv[i] - '0'));
if(*argv[i] == '+' || *argv[i] == '-' || *argv[i] == '*' || *argv[i] == '/')
{
y = pop(sq);
x = pop(sq);
printf("x: %d,y:%d\n",x,y);
switch(*argv[i])
{
case '+':
push(sq,x + y);
break;
case '-':
push(sq,x - y);
break;
case '*':
push(sq,x * y);
break;
default:
puts("intput error");
}
}
i++;
// printf("i:%d,%c\n",i,*argv[i]);
}
printf("%d\n",pop(sq));
return 0;
}
在程序中我們用直接從命令行輸入的方式。具體的算法就是我們上面描述的那樣里面運用的函數棧的創建（stack_create）,出棧（push），壓棧（pop）等就是我們課上所講的基礎程序。之前也很多同學提出，基礎程序熟練了可是就是不知道怎么用。其實在實際中棧和隊列的應用還是非常多的，所以希望同學們對所學的多去嘗試使用才能熟練。
下面是一個簡單的運行效果，同學們可以自己嘗試完善一下：
