栈

(1) 栈的实现!

操作规则：先进后出，先出后进。

1. int stack[N], top=0;       // top表示栈顶位置。

2. 入栈：inline void push(int a) { stack[top++]=a; }

3. 出栈：inline int pop() { return stack[--top]; }

4. 栈空的条件：inline bool empty() { return top<0; }

如果两个栈有相反的需求，可以用这种方法节省空间：用一个数组表示两个栈。分别用top1、top2表示栈顶的位置，令top1从0开始，top2从 N-1开始。

(2) DFS和栈

递归其实也用到了栈。每调用一次函数，都相当于入栈（当然这步操作“隐藏在幕后”）。函数调用完成，相当于出栈。

一般情况下，调用栈的空间大小为16MB。也就是说，如果递归次数太多，很容易因为栈溢出导致程序崩溃，即“爆栈”。

为了防止“爆栈”，可以将递归用栈显式实现。如果可行，也可以改成迭代、递推等方法。

使用栈模拟递归时，注意入栈的顺序——逆序入栈，后递归的要先入栈，先递归的要后入栈。

下面是非递归版本的DFS模板：

stack <int> s;						// 存储状态
void DFS(int v, …) { s.push(v);						// 初始状态入栈
while (!s.empty()) {   int x = s.top(); s.pop();  // 获取状态       // 处理结点   if (x达到某种条件)   {    // 输出、解的数量加1、更新目前搜索到的最优值等    …    return;   }   // 寻找下一状态。当然，不是所有的搜索都要这样寻找状态。   // 注意，这里寻找状态的顺序要与递归版本的顺序相反，即逆序入栈。   for (i=n-1;i>=0;i--)   {    s.push(… /*i对应的状态*/);   } } // 无解 cout<<"No Solution."; }