class MinStack
{
public:
  MinStack()//此时这个就是最小栈的构造函数（我们不写也没关系，因为构造函数编译器默认会对自定义类型初始化，内置类型不作处理）
  {}
  void push(int val)
  {
    _stack.push(val);
    if (_minstack.empty() || val <= _minstack.top())
    {
      _minstack.push(val);//满足条件要求， 就是此时的最小值，就入栈
    }
  }
  void pop()
  {
    if (_stack.top() == _minstack.top())//出栈过程，只要满足这个条件，就是表示是栈中的最小值
    {
      _minstack.pop();//想要删除最小栈中的数据，只有当上面的栈中的数据和下面的数据相等的时候，才可以删，不可以乱删
    }
    _stack.pop();//此时的这个删除数据跟我们的获取最小数据并没有关系（想要获取最小数据，只能是获取栈顶数据），删除的目的只是让这个栈拥有删除数据的能力
  }
  int top()
  {
    return _stack.top();
  }
  int getMinStack()
  {
    return _minstack.top();//这步就是根据原理之后，得到的答案的关键一步
  }
private:
  stack<int> _stack;
  stack<int> _minstack;
};  

class Solution
{
  bool IsPopOrder(vector<int> pushV, vector<int> popV)
  {
    stack<int> st;
    int pushi = 0, popi = 0;
    while (pushi < pushV.size())//此时因为我们的pushi（在数据一直不匹配的情况下），是要一直入数据的，但前提是小于题目给我们的vector数组的大小（没数据）
    {
      st.push(pushV[pushi++]);//此时表示的就是把pushV数组中的数据给入栈（当然此时是一个一个的入（并且是由pushi决定））例：此时pushV数组中的元素是：1 2 3 4 5 ，那么此时就是把 1 给入栈
      while (!st.empty() && st.top() == popV[popi])//然后把刚刚入栈的那个数据去和题目给我们的popV（出栈顺序）中的数据进行比较，假如此时的出栈顺序是 1 5 4 3 2，那么就导致此时刚刚入栈的顺序，满足出栈顺序，此时它就要出栈了，然后再去入pushV数组中的第二个数据2，然后发现，popV数组中的出栈顺序中第二个数据不是2而是5，所以此时，就不符合出栈要求，所以就要进行继续入栈的操作，直到把5给入栈，然后按照popV数组的顺序，把5给出栈
      {
        st.pop();//此时的这个删除和下面的popV数组下标popi加加，就是为了防止数据连续出栈（例： 4 3 2）的情况（支持循环判断），可以一直出数据
        popi++;//但是此时也要注意，在删除栈顶的时候，栈被删空了,所以想要进入这个循环就要加一个条件，就是判断栈是否为空（为空就不进入这个循环）
      }                                                                                     //在循环中再嵌套一个判断栈不为空的if语句也是可以的
      //代码来到这里，就表示需要入数据 ，例：此时是popV中出数据的顺序是5，那么此时就不满足，就需要先把 4 3 2 给入进去，就要调外层循环入数据
    }
    //return popi == popV.size();//popi走到尾，表示的就是出栈顺序判断完了（因为是一个一个和popV数组中的出栈顺序进行匹配，所以popi是需要一直向后走的）
    //和上述的原理一样，当我们把pushV数组中的元素全部给入进去之后，还是没有匹配到popV数组中要出的那个元素顺序，那么此时该popV数组就是有问题的
    return st.empty();//此时栈是空的也是可以判断的（如果栈为空，就表示符合popV数组的顺序，pushV数组中入栈的元素全部被删除了（也就是出栈了）），如果栈不为空，也就是没有找到匹配的顺序，出不了，栈就不为空
  }
};

namespace wwx
{
  template<class T, class Container = vector<T>>//此时的这第二个参数，本质上还是一个模板参数，名字是可以随便起的，但是因为此时该模板的作用是调用一个容器模板，所以此时就给了一个容器的英文单词（并且此时给了这个模板参数一个缺省参数）
  class stack//所以本质上模板参数和形参是一样的，只是此时的模板参数代表的是类型（什么什么类型），如果改成特定的类型，就跟普通的形参没有任何区别了
  {//就是对一个已有中的模式进行转换（类似于生活的对电力进行转换，降电压）并且此时涉及到一个叫设计模式的东西，大佬搞出来的，设计模式
  public:
    void push(const T& x)
    {
      _con.push_back(x);//此时就是往数组中入数据的意思（类似就是在入栈）
    }
    void pop()
    {
      _con.pop_back(); //入完数据，此时数组的最后一个数据就类似于我们的栈顶（所以使用尾删，就等于是在删除栈顶元素）
    }
    bool size()
    {
      return _con.size();
    }
    const T& top()//这种const引用真的很好用
    {
      return _con.back();//返回数组的尾部数据，就等于是在返回栈顶元素
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;//使用一个叫container的适配器来实现栈（类似就是一个vector的数据结构（因为栈不仅可以使用数组实现，也可以使用链表实现））
  };
  void test_stack1()
  {
    stack<int, vector<int>> st;//这种属于是数组栈
    //stack<int> st; //因为有缺省值，所以不传也可以（半缺省）
    //stack<int, list<int>> st;//这个叫链式栈（所以上述的那个适配器就是一个其它类型的数据结构，我们直接使用库里面已经实现了的数据结构来实现栈就行了）
    st.push(1);              //所以此时你想要实现什么类型数据结构的栈，你就给给什么类型的数据结构当作栈的适配器就行（当然最好的数据结构(适配器)是deque）
    st.push(2);              
    st.push(3);
    st.push(4);
    st.push(5);
    while (!st.empty())
    {
      cout << st.top() << " ";
      st.pop();
    }
    cout << endl;
  }
}
int main()
{
  wwx::test_stack1();
}

#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace wwx
{
  template<class T, class Container = list<T>>
  class my_queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);//此时就是往数组中入数据的意思（类似就是在入栈）
    }
    void pop()
    {
      _con.pop_front(); //这个位置是队列和栈的第一个区别（栈是队尾插入队尾出），而队列是队尾插入队头出
    }
    bool size()
    {
      return _con.size();
    }
    const T& front()//出队头数据
    {
      return _con.front();
    }
    const T& back()//出队尾数据
    {
      return _con.back();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;//使用一个叫container的适配器来实现栈（类似就是一个vector的数据结构（因为栈不仅可以使用数组实现，也可以使用链表实现））
  };
  //队列能不能用vector适配器呢？
  //这影响到我们可不可以使用vector实现队列
  //答案是不可以使用vector实现队列
  //原因：队列要支持尾插和头删（但是vector是不支持头删的（效率很低））
  void test_queue()
  {
    my_queue<int, list<int>> q;//由于用vector效率低，所以我们用list就行
    //stack<int> st; //因为有缺省值，所以不传也可以（半缺省）
    q.push(1);          
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    while (!q.empty())
    {
      cout << q.front() << " ";
      q.pop();
    }
    cout << endl;
  }
}
int main()
{
  wwx::test_queue();
}

  template<class T>
  class my_list//此时不是那种无哨兵位的单向非循环链表，而是带头双向循环链表
  {
    typedef list_node<T> node;//此时为了防止每一次把这个模板参数T给写漏掉（是类型不是类名），此时我们就直接把它给typedef一下，这样就非常的方便
  public:
    typedef __list_iterator<T, T&, T*> iterator;//此时里面这个类和外面那个类的本质区别就是，里面这个类，属于内部类（表示封装的迭代器类本质是my_list类的类），并且没有把外面那个typedef写进来的原因是，私有成员变量有用到，并不是都是给公有函数使用的，所以定义成全局类，提供给整个类使用（而迭代器类，私有成员变量用不上，所以就可以写成内部类的写法）
    typedef __list_iterator<T, const T&, const T*> const_iterator;//通过这种多一个模板参数的形式来实现同一个迭代器实现两中类型的迭代器调用
    //typedef __list_const_iterator<T> const_iterator;//这样我们就自己实现了一个const类型的迭代器，这样const类型的begin和end函数就可以使用const迭代器了
    iterator begin()
    {
      //iterator it(_head->_next);//此时的这句代码就是在调用上述的那个迭代器（使用上面的迭代器去帮我们构造一个it出来）
      //return it;//此时要注意，只有当传上来的值和修改的值都是自己本身的时候，才return *this,而当传上来的值是自己，都返回的值不是自己的时候（是重新构造出来的），此时就应该返回那个重新构造出来的结点
      //这边反而是不喜欢上述的写法，喜欢直接使用经典的匿名对象就行替换
      return iterator(_head->_next);
    }
    const_iterator begin()const
    {
      return const_iterator(_head->_next);
    }
    iterator end()//此时这个位置我们的end给给哨兵位的意思是，我们的迭代器是左闭右开的，迭代器中最后一个位置是最后一个数据的后一个位置（所以此时表示的就是哨兵位的位置，所以不是给给_head->prev，而就是哨兵位，因为此时end是迭代器中的end）
    {
      return iterator(_head);//使用_head去构造一个迭代器对象（匿名），就是去调用上述迭代器中的构造函数，然后用括号里面的这个结点去初始化一个新的结点(这个结点就是我要的结点)
    }
    const_iterator end()const
    {
      return const_iterator(_head);//此时为什么_head是const类型，还可以改变呢？原因：表示的是_head不可以改变，但是_head中的指针（_next/_prev）是允许指向别的东西的（所以可以改变），并且由于此时是涉及拷贝问题，所以也是允许拷贝的
    }
    void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    my_list()//带头双向循环链表 （明白此时的这个东西叫链表），所以遍历方式此时就只有使用迭代器，使用方括号和下标的方式纯属是搞笑的
    {//此时我们没有像源码一样，使用嵌套一个空初始化的函数，而是直接new
      //_head = new node;//此时这个的意思表示的是开辟一个哨兵位的头结点出来(但是要注意，new后面跟的一定是一个类型，所以我们的ListNode是一个模板类型，那么此时就需要把它的模板参数给带上)
      //_head->_next = _head;//然后此时让这个哨兵位的next指向自己
      //_head->_prev = _head;//哨兵位的prev指针也指向自己
      //此时有了一个专门用来初始化头结点的函数，所以直接调用就行
      empty_init();
    }//注意：一定要把类名和类型给区分开来，类名是类名，类型是类型，类名加上模板参数就是类型
    //这个位置还可以来一个迭代器类型的构造函数
    template<class iterator>
    my_list(iterator first, iterator last)//迭代器的构造函数
    {
      //但是由于，此时这个迭代器构造函数是需要有头结点才可以进行初始化，所以需要把头结点拿过来初始化一下   
      empty_init();//调函数初始化头结点
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //构造函数搞定之后，就是拷贝构造函数
    //my_list(const my_list<T>& lt)//记住，构造函数的本质就是为了去初始化另一个创建的还没初始化对象，所以给的就是此时这个类类型的一个变量
    //{//此时我们使用最现代的写法，不使用那种传统的写法了（就是通过遍历，插入，把另一个对象的数据拷贝到新对象中（由于是形参，所以不会改变函数外部中的数据））
    //  //lt1(lt2)//这个写法的话，此时的lt就是lt2，lt1就是this指针
    //  empty_init();
    //  for (auto e : lt)
    //  {
    //    push_back(e);
    //  }
    //}
    void swap(my_list<T>& tmp)//此时使用引用交换，就是经典的去指针化交换两个数据
    {
      std::swap(_head, tmp._head);//此时的_head（this）,本质上是要去调用初始化头结点，去把头结点初始化好之后，才可以进行交换
    }
    my_list(const my_list<T>& lt)//切记，此时的构造函数需要防止无限拷贝，所以不能进行传值调用，要使用传引用调用，把类和模板看成类型就行，例：string类
    {//构造函数超级现代化写法
      empty_init();//此时使用现代写法，是需要把this进行初始化的（初始化this之后，才可以让其去和tmp交换）
      my_list<T> tmp(lt.begin(), lt.end());//让tmp去调用拷贝构造（迭代器类型的构造函数）
      swap(tmp);//现代写法，窃取别人的劳动果实
    }
    //lt1 = lt3
    my_list<T>& operator=(my_list<T> lt)//此时这个位置不可以使用引用（因为此时赋值使用的是交换的方法（现代写法）），如果使用引用的话，就有会导致lt3中的值变成原来lt1中的值（如果不使用引用交换过程，就不会影响外部的lt3），并且此时lt3中开辟的空间会自动调用析构函数释放掉
    {
      swap(lt);//表示的意思就是把lt（lt3）的值赋值给lt1（this指针）
      return *this;//交换完之后lt3会自动调用析构函数释放掉
      //并且上述的构造函数可以使用传引用的原因是，我们使用的是tmp这个临时变量，让tmp通过（已经初始化的对象的地址）去调用迭代器类型的构造函数，所以本质上也没有改变外部的对象
    }
    ~my_list()
    {
      clear();//析构函数直接调用clear清理资源就行
      delete _head;//头结点也是new开辟出来的
      _head = nullptr;//置空防止别的东西会调用它（好习惯）
    }
    void clear()//清理资源调用这个函数就可以了
    {
      iterator it = begin();
      while (it != end())
      {
        it = erase(it);//链表的erase是会导致迭代器失效的，所以这里，我们就要接收它的下一个位置（删除后的位置）
        //erase(it++);//这样写也是可以的，因为此时的加加是list迭代器的加加，本质就是next（并且因为此时的是后置加加，返回的是形参，并不会改变it本身）
      }
    }
    //上述的知识比下面这些list功能的知识更重要(特别就是构造函数和拷贝构造函数，真的需要好好理解)
    void push_back(const T& x)//这种位置一定要搞清楚该函数的作用是什么，自然而然就知道了，我们传递的参数是什么，自然而然就知道怎么写了，最多就是多用了const+引用而已，并且一定要注意，此时的数据类型就是模板类型T
    {//这个就是普通的数据结构的写法，这边不需要太在意，带头双向循环链表，注意好头尾的位置就行
      node* tail = _head->_prev;//这句代码要注意，此时不是tail在控制_head->_prev,而是_head->_prev在控制_tail 
      node* new_node = new node(x);//注意好，此时的node是typedef过的（反正就是一个类类型的数据）例：string s1;
      tail->_next = new_node;//注意是双向循环
      new_node->_prev = tail;//注意是双向循环
      new_node->_next = _head;
      _head->_prev = new_node;//这样写就是一个经典的双向循环尾插（在哨兵位的前面找尾，然后插入，最快，根本不需要遍历）
    }
    void push_front(const T& x)
    {
      insert(begin(), x);//复用insert
      //如果是尾插的话，也是一个道理
      //insert(end(), x);//这里可以直接调用begin()或者end()的原因是，我们上述写了这两个函数，间接的通过_head获得了开始位置和最后位置
    }
    void insert(iterator pos, const T& x)
    {
      node* cur = pos._node;
      node* prev = cur->_prev;
      node* new_node = new node(x);
      prev->_next = new_node;
      new_node->_prev = prev;
      new_node->_next = cur;
      cur->_prev = new_node;
    }
    //void erase(iterator pos)//因为erase会导致迭代器失效，所以我们需要给一个返回值
    iterator erase(iterator pos)
    {
      assert(pos != end());//此时因为是带哨兵位的，所以不允许把哨兵位的头结点被删除(并且此时要注意的是，不可以用head去和pos比较，和pos比较需要是一个相同类型的迭代器才可以)
      node* prev = pos._node->_prev;
      node* next = pos._node->_next;
      prev->_next = next;
      next->_prev = prev;
      delete pos._node;
      return iterator(next);//此时就让next去构造，然后再返回（此时返回的就是下一个结点的地址啦）
    }
    void pop_back()
    {
      erase(--end());//意思是end返回了一个迭代器对象，然后让这个对象去调用减减运算符，调用减减运算符的本质就是在找该结点的前一个结点
    }                  //减减的本质是因为，此时的end是迭代器中的end，是最后一个数据的下一个数据（_head），所以需要减减一下，表示的才是最后一个尾结点
    void pop_front()
    {
      erase(begin());
    }
  private:
    //struct ListNode* _head;//在C语言中正常的写法是这样的，但是在C++中的时候，就可以发现，我们不一定要跟上struct也可以
    //ListNode* _head;//记得因为是模板类型，所以要跟上模板参数
    node* _head;//看到这个就要注意是typedef过的
  };