1.3：背包队列和栈

一：算术表达式求值

这次讲的是简单的算术表达式求值，怎么简单呢？就是每个子表达式都是有括号的，你不用去管它的运算优先级
栈永远是表达式求值的经典应用
我们求的是类似这样的表达式：( 1 + ( (2+3) ( 4 5) )) 空格忽略（我是为了md格式方便显示）
我们使用栈的求值策略如下：
准备两个栈，分别存放数值和运算符，当我们从左到右扫描表达式时有四种情况，我们来分别处理：

遇到数->直接入数值栈
遇到运算符->直接入运算符栈
遇到左括号->忽略

遇到右括号，弹出一个运算符，弹出俩数，做运算（注意顺序），将结果压入数值栈
我们可以看到，非常简单对吧？为毛这样就解决了呢，其实推理起来也简单，我们在遇到一个右括号了，就说明我们已经得到了一个被括号包围的子表达式，那我们把它算出来就是一个数了，再把这个数入栈去替代了原来的子表达式，举个例子，我们用5去替代了(2+3)，就是这意思
下面我们来给出代码：

double evaluate(vector<string> args)
{
 stack<string> val;
 stack<string> ops;
 for(int i=0; i<args.size(); ++i)
 {
     string one = args[i];
     if(one == "(") //左括号忽略
     else if(one == "+" || one == "-" || one == "*" || one == "/") //运算符压入运算符栈
     {
         ops.push_back(one);
     }
     else if(one == ")")
     {
         double first = val.pop(); //不管数据格式
         double second = val.pop(); //注意顺序
         string op = ops.pop();
         val.push_back(second op first); //你懂就好。。。
     }
     else
     {
         val.push_back(one); //遇到数，压入数值栈
     }
 }
 return val.pop(); //最后的结果在数值栈，就剩一个数了
}

二：链表实现栈

我们来实现一个class（有错就提哈）：

class Stack
{
private:
    //链表节点定义
    template <typename Item>
    class Node
    {
    public:
        Item item; //节点内容
        Node* next; //指向下一个的指针
    };
    Node first; //栈顶：最近添加的元素
    int N; //元素数量

public:
    bool isEmpty(){return first == null;}
    int size(){return N;}

    void push(Item &t)
    {
        Node oldfirst = first; //记录当前栈顶
        first = new Node(); //新建一个节点作为栈顶
        first.item = item; //赋值新栈顶
        first.next = &oldfirst; //把新栈顶和老栈顶连起来

        ++N; //更新栈内元素数量
    }

    T& pop()
    {
        Item t = first.item; //拷贝弹出的栈顶
        first = *(first.next); //更新栈顶元素
        --N; //更新栈内元素数量
        return t; //返回原栈顶元素
    }
};

三：链表实现队列

栈是先入后出(first in last out)，队列是先进先出(first in first out)：

class Queue
{
private:
    Node first; //这里的Node就跟上面的一样，不重复了
    Node last; //这里要保存last，因为插入是队尾，删除是队头，都不能少
    int N;

public:
    bool isEmpty(){return first == null;}
    int size(){return N;}

    void enqueue(Item &item) //向队尾添加元素
    {
        Node oldlast = last; //记录原尾节点
        last = new Node(); //新建一个节点作为尾节点
        last.item = item; //把传入的参数赋值给新尾节点
        last.next = null; //新尾节点的指针为null

        if(isEmpty()) {first = last;} //如果为空，就是first==null，直接把last赋值给它就好
        else {oldlast.next = last;}//把新来的尾节点接上去

        ++N; //更新节点数量
    }

    Item& deque() //从表头删除元素，保证至少有一个元素
    {
        Item item = first.item; //记录原表头，要返回的
        first = first.next; //表头的下一个作为新表头

        if(isEmpty()) {last = null;}
        --N;
        return item;
    }
};

四：经典题型：哪种顺序不可能

来一道经典习题

将整数0到9按顺序压入栈，在压入过程中可随时出栈，下面哪种序列是不可能产生的：

a. 4321098765
b. 4687532901
c. 2567489310
d. 4321056789
e. 1234569870
f. 0465381729
g. 1479865302
h. 2143758790
一开始我碰到这些题的时候，觉得比较简单，只要在脑中（或者纸上）模拟一个栈，然后按照题目给的出栈顺序走一遍，行就是对的，不行就是错的，比如对于a，第一个出栈的是4，那我先让0-4依次入栈，然后4出来，3210接着出来，然后下一个出来的是9，那我就要把剩下的5-9全部入栈，再依次出栈，刚好，所以a是对的

但是这个题有这么多，想想也是蛮烦的，所以我就想了个方法，我总结了一个小结论，是很容易根据栈的特性来推导的，我们根据这个小结论会很容易判断以上那些序列哪个合法哪个不合法：
在右边比x小的数，一定是递减排列的
解释一下，这个x是你在序列中任意选的数，

比方说a中我选个9，在9右边的都是比它小的8765，正好递减，所以对于9来说，它是合法的，
再比如b中，我选个9，右边比它小的是01，不是递减，b不合法（不信你试试），
再比如f中，我选个8，右边比它小的是172，显然不是递减，所以f错了为什么这样能判断呢？

解释一下：在x右边的，也就是比x晚出栈的，根据先入后出，它们一定是比x早进去的，又因为进去的时候序列是递增的，所以它们出来一定是递减的