数据结构学习笔记——第四章：栈

一、栈

1. 栈的特点

  ①只有最右侧（顶部）元素可见，最左侧（底部）元素不可见
  ②只提供pop和push两个接口用于操作顶部元素
  从形式上看，栈就像堆积凳子或者盘子，last in first out。

2. 栈的实现

  栈的实现可以借助之前已经实现过的Vector类。具体而言就是以Vector类为父类派生出一个子类Stack，然后只需要在Stack类中调用父类的接口，实现栈的pop、push和top即可。

二、栈的应用

  栈适用于以下特点的算法：

• 计算过程与输出过程相反

• 计算深度难以预估

  
  栈混洗的禁形

• 结论：
    元素所能构成的合法栈混洗的个数等于n对括号所能构成的合法匹配的个数，即

• 算法：
    ①对待检查的栈B进行遍历，在每次遍历开始时判断原栈A是否为空，若不为空则将原栈最上方元素压入中间栈S。
    ②判断S与B的顶部元素是否相同。若相同则S和B将顶部元素弹出；
    ③若不同，则持续将A的首元素压入S中，直到A的首元素和B的首元素相同为止。（注意要先确保A不为空）
    ④当A为空时结束循环。判断此时S是否为空栈，若为空则栈混洗。若不为空，判断S和B中的首元素是否相同：不同则不是栈混洗；相同则为栈混洗。

• 代码：

template <typename T>
T pop(stack<T> &stk){
    T tp = stk.top();
    stk.pop();
    return tp;
}

template <typename T>
bool is_shuffled(stack<T> targ, stack<T> org){
    stack<T> temp;
    while(!targ.empty()){
        if(!org.empty()) temp.push(pop(org));
        else break;
        cout<<"targ: "<<targ.top()<<" temp: "<<temp.top()<<endl;
        if(targ.top() == temp.top()){
            targ.pop();
            temp.pop();
        } else{
            while(!org.empty() && targ.top() != org.top())
                temp.push(pop(org));
        }
    }
    if(temp.empty()) return true;
    return temp.top() == targ.top() ?
            true: false;
}

int main(){
    int A[]={1,2,3,4,5};
    //int B[]={1,3,2,4,5}; //not permutaed
    //int B[]={2,1,3,4,5}; //permutaed
    int B[]={2,1,3,5,4}; // not permutated
    auto size_A = getArrayLen(A);
    auto size_B = getArrayLen(B);
    stack<int> org;
    stack<int> targ;
    for(int i=0;i<size_A;++i) org.push(A[i]);
    for(int i=0;i<size_B;++i) targ.push(B[i]);
    bool rst = is_shuffled(targ, org);
    cout<<((rst) ? "A is permutated from B!":"A is not permutated from B.")<<endl;
}

• 输出：

➜ compile_gcc stack_permutation.cpp && ./stack_permutation
targ: 4 temp: 5
targ: 4 temp: 4
targ: 5 temp: 3
A is not permutated from B.