Chapter 3 Stacks and Queues

“The Rules"

1.C++ STL中<stack>与<queue>的常用函数：
<stack>: empty(),pop(), top(),push(const val_type &);
<queue>:empty(),pop(),front(),push(const val_type &);

2.stack 与 queue 可以视作封装好的Linked list，限制了访问和插入的自由。因此适用stack或queue的情境，也可以考虑使用更为强大的list。

3.stack与Recursion的关系：recursion在底层用stack实现。入栈操作等价于递归调用，出栈操作等价于递归返回。出入栈操作的对象，即为当前等待先后解决的的subproblem。

模式识别

1.用stack实现依赖顺序读取的功能
stack具有LIFO的特性，如需实现任何依赖顺序或随机读取的常规操作，往往可以借助两个stack"同向"或"反向"来实现。( 反向时，往往需要互相"倾倒"来实现特定顺序。）

e.g. 1 Design a stack with push(), pop() and min() in $O(1)$ time. ( CtCI 3.2 )
e.g. 2 Implement a queue with two stacks.( CtCI 3.5 )
e.g. 3 Sort a stack in ascending order with an additional stack.( CtCI 3.6)

2."Save for later"问题
关于"收敛结构"与"发散结构"的解释，详见"Chapter 7 Recursion and Dynamic Programming"。

处理收敛结构问题，如果无论从哪一端出发，都避免不了"（部分）当前节点的解依赖后驱节点"（也就是说，当前节点，如果不能获知后驱节点，就无法得到有意义的解），那么可以用backtracking（如果前进方向已知），或stack（或等同于stack的若干个临时变量）解决。当前节点入栈，直到依赖的所有节点都完备时再取出求解，必要时将结果再次入栈。

e.g.1 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. ( Leetcode: Valid Parentheses )
e.g.2 Evaluate a Postfix Notation (Reverse Polish Notation)

//Reverse Polish Notation (RPN)
double rpn(stringstream &input){
    string tok;
    double val;
    stack<double> res;
    while(input>>tok){
        if( isdigit(tok[0] ){
            streamstream tmp(tok);
            tmp >> val;
            res.push(val);
        }
        switch(tok[0]){
            case '*':
                val = res.top();
                res.pop();
                val = res.top() * val ;
                res.pop();
                res.push( val );
                break;
            ...
        }
    }
    return res.top();
}

e.g.3 Evaluate a Prefix Notation (Polish Notation)

double pn(stringstream& input) {
    string tok;
    input >> tok;
    double res;
    switch (tok[0]) { 
       case '+': return pn(input) + pn(input);
       case '-': return pn(input) - pn(input);
       case '/': return pn(input) / pn(input);
       case '*': return pn(input) * pn(input); 
    }
    stringstream tmp(tok);
    if( isdigit(tok[0]) )
        tmp >> res;
    return res;
}

用stack求解的办法，参见 http://stackoverflow.com/questions/3205723/how-to-evaluate-an-expression-in-prefix-notation/13781413#13781413

3.用stack解决Top-Down的发散结构问题

用Recursion解决Top-Down的发散结构问题，详见Chapter 7。

在使用D&C策略时，如果每个subproblem，处理的是单个同样类型的object，则可以将该object按照Top-down的方向入栈，然后循环pop()来访问。如果subproblem的size不同，则可将他们声明为同种类型的object，按照Top-Down的方向入栈；最后pop()访问时，再将复合的subproblem拆解，push入栈；如此循环直至stack清空。（类似queue结构在BFS中的作用）

e.g.1 Binary Search Tree In-Order Traversal Iterative

 void inorderTraversal(TreeNode *root) {
        if(root == NULL)
            return;
        stack<TreeNode *> st;
        while(!st.empty() || root ){
/* The 3 Nodes: root, left and right can actually be regarded as 3 subtrees( same type ), though we did little optimization here so we only push 1 subtree instead of 3 at one time( always the root ).*/
            if(root){
                st.push(root);
                root = root->left;
            }else{
                root = st.top();
                st.pop();
                visit( root );
                root = root->right;
            }
      }
}

e.g.2 Solve the Hanoi Tower problem without recursion

enum Tower { Zero,Left, Mid, Right};
class HanoiObj{
public:
   Tower src,tmp,dest;
   int num,index;
   HanoiObj(Tower s,Tower t,Tower d,int n):src(s),tmp(t),dest(d),num(n){
       if(n == 1) index = 1;
   }
   HanoiObj(Tower s,Tower d,int i):src(s),dest(d),index(i){
       num = 1; tmp = Zero;
   }
};
void move( Tower src, Tower dest,int index){
   cout << "Move Disk #" << index <<" from Tower " << src << " to Tower " << dest << endl;
}
void TOH(int N, stack<HanoiObj*>&Hstack){
   Tower s,t,d;
   int n;
   Hstack.push(new HanoiObj(Left,Mid,Right,N));
   while( !Hstack.empty()){
       HanoiObj *tmpObj = Hstack.top();
       Hstack.pop();
       s = tmpObj->src;
       t = tmpObj->tmp;
       d = tmpObj->dest;
       n = tmpObj->num;
       if(n < 1) continue;
       if(n == 1)
           move(s,d,tmpObj->index);
       else{
           Hstack.push(new HanoiObj(t,s,d,n-1));
           Hstack.push(new HanoiObj(s,d,n));
           Hstack.push(new HanoiObj(s,d,t,n-1));
       }
       delete tmpObj;//
   }
}