从0开始学算法--数据结构（2.1栈）

栈的理解：

       栈就是一像放在地上的羽毛球桶，现在有各种颜色的羽毛球，你有4个操作，1，把一个羽毛球放在桶里，2，看看桶顶的羽毛球是什么颜色的（你只能看到桶顶的那个），3，把桶顶的羽毛球取出来，4，看看羽毛球桶是空的，满的，还是有羽毛球且不满。

添加一个元素

void push(int x){//给栈加一个为x的元素
    s[++top]=x;
}

删除一个元素

int pop(){//删除堆顶元素
    top--;
    return s[top+1];
}

返回堆顶元素

int top(){//返回堆顶元素
    return s[top];
}

例一：计算逆波兰表达式（我们平时用的是中缀表达式（ 1 + 2 ） * （ 5 + 4 ） ，改为逆波兰表达式为1 2 + 5 4 + *。逆波兰表达式的优点在于不用加括号 ）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

const int maxn=1e5+10;

int top,s[maxn];

void push(int x){//给栈加一个为x的元素
    s[++top]=x;
}

int pop(){//删除堆顶元素
    top--;
    return s[top+1];
}


int main(){
    int a;
    int b;
    top=0;
    char x[maxn];
    while(scanf("%s",x)!=EOF){
        if(x[0]=='+'){
            a=pop();
            b=pop();
            push(a+b);
        }else if(x[0]=='-'){
            b=pop();
            a=pop();
            push(a-b);
        }else if(x[0]=='*'){
            a=pop();
            b=pop();
            push(a*b);
        }else{
            push((int)atoi(x));
        }
    }
    printf("%d\n",pop());
    return 0;
}