普通栈

大家在用浏览器打开网页的时候，时常会点击页面上的某个链接继续浏览，又会在新的页面上，点个链接跳转到另一个新页面。另外，如果想回到上一个页面，就会点击浏览器的“返回”按钮，再点击一下就会返回上一个页面的上一个页面，而且每次点击“返回”只能返回上一级。大家有没有想过浏览器的这个功能是怎么实现的呢？

浏览器的这个功能可以用栈来实现，当前浏览的页面我们叫它为栈顶元素，跳转到一个新页面我们叫元素入栈，点击“返回”按钮我们叫元素出栈，当然出栈前提是栈里要有元素，比如在浏览器里，如果已经返回到了最开始的页面，那就无法返回了。栈有一个重要的性质，就是先进后出，First In Last Out(FILO)。

什么是先进后出？在浏览器的例子里，先打开的页面的一定是到后面才会被返回到，后面打开的页面一定是先被返回到的。这个过程，我们可以用栈这种数据结构来模拟实现。
First In Last Out(FILO)

#include<iostream>
#include<string>
#include<cassert>
using namespace std;
template<class Type> class Stack {
private:
    Type *urls;
    int max_size, top_index;
public:
    Stack(int length_input) {
        urls = new Type[length_input];
        max_size = length_input;
        top_index = -1;
    }

分析：栈维护一个数组 urls[ ]
      一个容量max_size(元素个数，
      而不是最大数组下标)
      一个整数记录栈顶位置 top_index

    ~Stack() {
        delete[] urls;
    }
//入栈 
    bool push(const Type &element) {
        if (top_index >= max_size - 1) {
            return false;
        }
        top_index++;
        urls[top_index] = element;
        return true;
    }
解析：入栈前判断是否非法
          然后直接 top_index++把元素入栈就行
//出栈 
 bool pop() {
        if (top_index < 0) {
            return false;
        }
        top_index--;
        return true;
    }
//栈顶元素
    Type top() {
        assert(top_index >= 0);
        return urls[top_index];
    }
//是否为空
    bool empty(){
        if(top_index<0){
            return true;
        }else{
            return false;
        }

    }


};
int main() {
    int n,num;
    cin>>n;
    Stack<int> stack(n);
    for(int i=1;i<=n;i++)
    {
     cin>>num;
        stack.push(num);
    }
    while(!stack.empty()){
      cout<<stack.top()<<" ";
        stack.pop();
    }
    return 0;
}

单调栈：

单调栈顾名思义，单调栈就是栈内元素单调递增或者单调递减的栈，这一点和单调队列很相似，但是单调栈只能在栈顶操作。

为了帮助大家更好理解单调栈，我们借用拿号排队的场景来说明下。现在有很多人在排队买蒜味可乐，每个人手里都拿着号，越靠前的人手里的号越小，但是号不一定是连续的。蒜头君拿了号后并没有去排队，而是跑去约会了。等他回来后，发现队伍已经排得很长了，他不能直接插入到队伍里，不然人家以为他是来插队的。蒜头君只能跑到队伍最后，挨个询问排队人手里的号，蒜头君认为号比他大的人都是“插队”的，蒜头君就会施魔法把这些人变消失，直到蒜头君找到号比他小的为止。

在上面这个场景里，大家排的队伍就像是单调栈，因为大家手里拿的号是单调递增的。蒜头君找自己位置的这个过程就是元素加入单调栈的过程。新加入的元素如果加到栈顶后，栈里的元素不再是单调递增了，那么我们就删除加入前的栈顶元素，就像蒜头君施魔法把“插队”的人变消失一样。直到新元素加入后，栈依然是单调递增时，我们才把元素加进栈里。