栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（top），它是后进先出（LIFO）的。对栈的基本操作只有push（进栈）和pop（出栈）两种，前者相当于插入，后者相当于删除最后的元素。
由于栈在本质上是一种受限制的表，所以可以使用任何一种表的形式来实现它，我们最常使用的一般有两种：
链表
数组
它们在复杂度上的优缺点对比如下：
新增和删除元素时的时间复杂度
链表：在动态申请内存（new或者malloc）上的花销非常昂贵。
数组：几乎没有花销，以常数O(1)时间运行，在带有自增和自减寻址功能的寄存器上操作时，编译器会把整数的push和pop操作编译成一条机器指令。
空间复杂度
链表：由于空间是动态申请、释放的，因此不会浪费空间，而且只要物理存储器允许，理论上能够满足最大范围未知的情况。
数组：必须在初始化时指定栈的大小，有可能会浪费空间，也有可能不够空间用。
结论：
如果对运行时的效率要求非常高，并且能够在初始化时预知栈的大小，那么应该首选数组形式；否则就应该选用链表形式。
由于对栈的操作永远都是针对栈顶（top）进行的，因此数组的随机存取的优点就没有了，而且数组必须预先分配空间，空间大小也受到限制，所以一般情况下（对运行时效率的要求不是太高）链表应该是首选。
栈的实现如下：
/////////////////////////////////////////////////////////////////////////////// // // FileName : stack.h // Version : 0.10 // Author : Luo Cong // Date : 2005-1-6 11:42:17 // Comment : // /////////////////////////////////////////////////////////////////////////////// #ifndef __STACK_H__ #define __STACK_H__ #include "../../slist/src/slist.h" template<typename T> class CStack : public CSList<T> { public: int push(T data); int pop(T *data = NULL); int top(T *data) const; }; template<typename T> inline int CStack<T>::push(T data) { return AddTail(data); } template<typename T> inline int CStack<T>::pop(T *data) { if (IsEmpty()) return 0; if (data) top(data); RemoveTail(); return 1; } template<typename T> inline int CStack<T>::top(T *data) const { ASSERT(data); if (IsEmpty()) return 0; *data = GetTail(); return 1; } #endif // __STACK_H__
调用如下：
/////////////////////////////////////////////////////////////////////////////// // // FileName : stack.cpp // Version : 0.10 // Author : Luo Cong // Date : 2005-1-6 11:42:28 // Comment : // /////////////////////////////////////////////////////////////////////////////// #include <iostream> #include "stack.h" using namespace std; static void PrintValue(const int nRetCode, const int nValue) { if (nRetCode) cout << nValue << endl; else cout << "Error occured!" << endl; } int main() { CStack<int> stack; int nValue; int nRetCode; #ifdef _DEBUG _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #endif stack.push(1); stack.push(2); stack.push(3); nRetCode = stack.top(&nValue); PrintValue(nRetCode, nValue); nRetCode = stack.pop(&nValue); PrintValue(nRetCode, nValue); nRetCode = stack.pop(&nValue); PrintValue(nRetCode, nValue); nRetCode = stack.pop(&nValue); PrintValue(nRetCode, nValue); }
上面的代码就是在单链表的基础上实现的栈，您会看到，在C++的继承机制下，栈的实现简单得可怕。 :)
一个影响栈的运行效率的问题是错误检测。我的栈实现中是仔细地检查了错误的——对空栈进行top和pop操作，以及当存储空间不够时进行push操作是会引起异常的，显然，我们不愿意出现这种情况，但是，如果把对这些条件的检测放到代码中，那就很可能要花费像实际栈操作那样多的时间。由于这个原因，除非在错误处理极其重要的场合（例如在操作系统中），一般在栈中省去错误检测就成了普通的惯用手法。
但我认为，一个良好的程序首先应该是健壮的，这比效率还要重要，特别是对于栈这种最基本的数据结构，它很可能会被作为基本的元素而被别的地方大量地使用。所以我并没有因为效率的问题而省去了错误检查机制。
引入错误检查机制的代价是：
对top和pop的操作变得有些繁琐。在代码中我是使用了返回值0或者1来表示成功或者失败，而实际的栈顶元素是通过参数来返回的。这样做必定会有人不满——太麻烦了！但这是我能想到的最好的解决方法，如果你有更好的方法，请告诉我。
运行时效率会降低。如果确实耗费了太多的时间，你可以把错误检查去掉，但前提条件是你能确保整个运行过程中不会出错——其实还是要有错误检查的，只不过这些错误检查会放在外围来做而已。
好了，就说那么多，下面我们来看看栈的应用。
对栈的应用实在是太广泛了（谁让栈是最基本的数据结构元素之一呢？），例如有平衡符号、表达式转换之类的，我们在这里就选择一个比较有实用价值的例子——中缀到后缀表达式的转换。（可以用在编译器等地方）
/////////////////////////////////////////////////////////////////////////////// // // FileName : postfix.cpp // Version : 0.10 // Author : Luo Cong // Date : 2005-1-6 16:00:54 // Comment : // /////////////////////////////////////////////////////////////////////////////// // 算法： // 1)检查输入的下一元素。 // 2)假如是个操作数，输出。 // 3)假如是个开括号，将其压栈。 // 4)假如是个运算符，则 // i) 假如栈为空，将此运算符压栈。 // ii) 假如栈顶是开括号，将此运算符压栈。 // iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。 // iv) 否则栈顶运算符出栈并输出，重复步骤4。 // 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。 // 6)假如输入还未完毕，跳转到步骤1。 // 7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。 #include <stdio.h> #include "stack.h" // 返回操作符的优先级 // +和-的优先级是一样的，*和/的优先级也是一样的，但+和-的优先级要比*和/的低。 static int GetPRI(const char optr) { switch (optr) { case '+': return 1; case '-': return 1; case '*': return 2; case '/': return 2; default : return 0; } } // 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比， // 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。 static void ProcessStackPRI( CStack<char> &stack, const char optr, char **szPostfix ) { ASSERT(*szPostfix); int i; int nRetCode; char chStackOptr; int nCount = stack.GetCount(); for (i = 0; i <= nCount; ++i) { nRetCode = stack.top(&chStackOptr); if ( (0 == nRetCode) || // 栈顶为空，新操作符添加到栈顶 (GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低 ) { stack.push(optr); break; } else { // 如果栈顶操作符优先级不低于当前的，则栈顶元素出栈并输出： stack.pop(); *(*szPostfix)++ = chStackOptr; } } } static void Infix2Postfix( const char *szInfix, char *szPostfix ) { ASSERT(szPostfix); char chOptr; int nRetCode; CStack<char> stack; while (*szInfix) { switch (*szInfix) { // 忽略空格和TAB： case ' ': case '\t': break; // 对操作符进行优先级判断，以便决定是入栈还是输出： case '+': case '-': case '*': case '/': nRetCode = stack.IsEmpty(); if (!nRetCode) ProcessStackPRI(stack, *szInfix, &szPostfix); else stack.push(*szInfix); // 当栈为空时，毫无疑问操作符应该入栈 break; // 遇到左括号时，无条件入栈，因为它的优先级是最高的 case '(': stack.push(*szInfix); break; // 遇到右括号时，逐个把栈中的操作符出栈，直到遇到左括号为止 case ')': do { nRetCode = stack.pop(&chOptr); if (nRetCode && ('(' != chOptr)) // 左括号本身不输出 *szPostfix++ = chOptr; } while (!stack.IsEmpty() && ('(' != chOptr)); // 遇到左括号为止 break; // 其余的情况，直接输出即可 default: *szPostfix++ = *szInfix; break; } ++szInfix; } // 如果输入的内容已经分析完毕，那么就把栈中剩余的操作符全部出栈 while (!stack.IsEmpty()) { nRetCode = stack.pop(&chOptr); *szPostfix++ = chOptr; } *szPostfix = '\0'; } int main() { char *szInfix = "a+b*c+(d*e+f)*g"; char szPostfix[255]; #ifdef _DEBUG _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #endif Infix2Postfix(szInfix, szPostfix); printf("Infix : %s\n", szInfix); printf("Postfix : %s\n", szPostfix); }
源代码里面已经有了详细的注释，我就不再罗嗦了。我只做了+、-、*、/四种操作符的转换，另外，如果括号不匹配，例如有左括号但是没有右括号，或者反过来，程序就可能会运行不正确，但这不是我写这个例子的重点，我写它只是为了掌握栈的用法，如果您有兴趣，可以试着完善它。
下面给出两个例子：
中缀表达式：a + b * c + (d * e + f) * g 后缀表达式：abc*+de*f+g*+
中缀表达式：2 * (x + y) / (1 - x) 后缀表达式：2xy+*1x-/