四、棧（Stack）
前一篇講解了最基本的東西，這篇就稍微前進一點點，講一下棧，棧在英文中叫Stack，翻譯成中文又叫“堆棧”，但決不能稱為“堆”，這個要搞清楚，我們說的“棧”和“堆棧”指的都是Stack這種數據結構，但“堆”卻是另外一個概念了，這里且不提。
棧最大特點是先進后出，如圖：
可以看出，棧有幾個最常見的方法，或者說必備的方法，Push，Pop和Top，即進棧，出棧和取最頂元素。從代碼上看，棧如何實現呢？用數組好還是用單向鏈表好呢？其實都可以，我下面的例子是用數組實現的。
說了那么多，棧有什么用呢？下面就舉一個最經典的例題——逆波蘭表達式（RPN，Reversed Polish Notation）的求解。
什么是逆波蘭表達式？我們表述一個算式通常是這樣：X+Y，即：“操作數1 操作符 操作數2”，當然也有比較特別的，比如“sqrt(N)”，sqrt是操作符，N是操作數，而逆波蘭表達式則很統一，先操作數，后操作符，為什么叫“逆波蘭表達式”？因為有一個波蘭人發明了波蘭表達式，而逆的波蘭表達式就叫“逆波蘭表達式”了。看下圖就能很好理解了：
所有的算式都可以用逆波蘭表達式寫出來，只是我這里的舉例是為了方便起見，限制在整數的四則運算里。
那假如現在我們有一個逆波蘭表達式，那我們如何求出它的值呢？這里我們的“棧”就要派上用場了，由于操作數在操作符前面，所以我們按順序遍歷這個表達式，遇到操作數的時候進棧，遇到操作符時候讓操作數出棧并運算，然后把運算結果進棧。過程如下圖所示：
遇到第一個操作符，“+”的時候，由于需要兩個操作數，所以出棧兩次，4和3出棧，執行加法運算，結果是7，7進棧……依此類推。
下面我給出參考代碼，我的代碼使用很簡單，復制，粘貼到一個cpp文件中，編譯此cpp文件即可，沒別的依賴。
#include "stdio.h"
struct Cell
{
int iType; // 0 - number, 1 - '+', 2 - '-', 3 - '*', 4 - '/'
int iData;
};
class Stack
{
public:
Stack(int iAmount = 10);
~Stack();
//return 1 means succeeded, 0 means failed.
int Pop(int& iVal);
int Push(int iVal);
int Top(int& iVal);
private:
int *m_pData;
int m_iCount;
int m_iAmount;
};
Stack::Stack(int iAmount)
{
m_pData = new int[iAmount];
m_iCount = 0;
m_iAmount = iAmount;
}
Stack::~Stack()
{
delete m_pData;
}
int Stack::Pop(int& iVal)
{
if(m_iCount>0)
{
--m_iCount;
iVal = m_pData[m_iCount];
return 1;
}
return 0;
}
int Stack::Push(int iVal)
{
if(m_iCount<m_iAmount)
{
m_pData[m_iCount] = iVal;
++m_iCount;
return 1;
}
return 0;
}
int Stack::Top(int& iVal)
{
if(m_iCount>0 && m_iCount<=m_iAmount)
{
iVal = m_pData[m_iCount-1];
return 1;
}
return 0;
}
int main(int argc, char* argv[])
{
//12 3 4 + * 6 - 8 2 / +
Cell rpn[11] = {
0, 12,
0, 3,
0, 4,
1, 0,
3, 0,
0, 6,
2, 0,
0, 8,
0, 2,
4, 0,
1, 0};
Stack st;
// I won't check the return value for this is just a demo.
int i, iOpt1, iOpt2;
for(i=0; i<sizeof(rpn)/sizeof(Cell); i++)
{
switch(rpn[i].iType)
{
case 0: // number
st.Push(rpn[i].iData);
break;
case 1: // +
st.Pop(iOpt2);
st.Pop(iOpt1);
st.Push(iOpt1 + iOpt2);
break;
case 2: // -
st.Pop(iOpt2);
st.Pop(iOpt1);
st.Push(iOpt1 - iOpt2);
break;
case 3: // *
st.Pop(iOpt2);
st.Pop(iOpt1);
st.Push(iOpt1 * iOpt2);
break;
case 4: // /
st.Pop(iOpt2);
st.Pop(iOpt1);
st.Push(iOpt1 / iOpt2);
break;
}
}
int iResult;
st.Pop(iResult);
printf("The result is %d\n", iResult);
return 0;
}
（未完待續……）