算法————双栈实现队列、双队列实现栈、实现一个栈Push（出栈）Pop（入栈）Min（返回最小值的操作）的时间复杂度为O(1)

---

---

一.双栈实现队列

1.思路原理：队列的特点，先进先出；栈的特点，后进先出；原理刚好相反，那么无非是俩个栈互相“倒“或者“导”，这都不是重点了，有了这个初步思路我们就得想办法来实现如何倒了。

2“倒”或者“导”思路图：

法①：核心原理：每次插入都得倒回popstack栈的所有元素,最后所有的元素回归popstack

法一代码：

template<class T>
class QueueByTwoStack
{
    //从插入开始一直将popstack先倒回到Pushstack然后再插入，再倒回。
public:
    void Push(const T& data)//法一检查popstack是否有未倒回的的元素，然后倒回并插入
    {
            while (!PopStack.empty())
            {
                PushStack.push(PopStack.top());
                PopStack.pop();
            }
            PushStack.push(data);
            while (!PushStack.empty())//插入后重新倒回
            {
                PopStack.push(PushStack.top());
                PushStack.pop();
            }
    }
    void Pop()
    {
        assert(!PopStack.empty());
        PopStack.pop();
    }
    T& Front()
    {
        return PopStack.top();
    }
    size_t Size()
    {
        return PopStack.size() + PushStack.size();
    }
    bool Empty()
    {
        return (PopStack.empty() && PushStack.empty());
    }
protected:
    stack<T> PushStack;
    stack<T> PopStack;
};

法②：直接将数据插入pushstack中；需要出队时将popstack的元素出栈，当popstack为空时，将pushstack导入popstack中

法二代码：

template<class T>
class QueueByTwoStack1
{
public:
    void Push(const T& data)
    {
        pushstack.push(data);
    }
    void pop()
    {
        if (!popstack.empty())
        {
            popstack.pop();
        }
        else if (!pushstack.empty())//导入
        {
            while (!pushstack.empty())
            {
                popstack.push(pushstack.top());
                pushstack.pop();
            }
            popstack.pop();
        }
    }
    T& Front()
    {
        if (!popstack.empty())//判断
        {
            return popstack.top();
        }
        else if (!pushstack.empty())//导入
        {
            while (!pushstack.empty())
            {
                popstack.push(pushstack.top());
                pushstack.pop();
            }
            return popstack.top();
        }
    }
    size_t Size()
    {
        return popstack.size() + pushstack.size();
    }
    bool Empty()
    {
        return (popstack.empty() && pushstack.empty());
    }
protected:
    stack<T> pushstack;
    stack<T> popstack;
};

---

---

二.双队列实现栈

关于队和栈的特点上面已经讲过，这里就不重复，还是利用他们的特点来实现，这里就直接上思路吧！

思路图：

代码实现：

#pragma once;
#include<iostream>
using namespace std;
#include<queue>
//stack的特点后进先出，队的特点先进先出；
//队是尾插头删；
//所以在队尾存的就是最后进来的元素；实现：
//利用俩个队相互倒，每次非空队的元素导入空栈只留一个元素即就为栈顶元素；
//重点：无论任何操作始终要保持有一个队列为空
template<class T>
class StackByTwoQueue
{
public:
    void Push(const T& data)
    {
        if (q1.empty() && !q2.empty())//默认q1为非空队
        {
            queue<T> tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        q1.push(data);
    }
    void Pop()
    {
        //默认q1为非空队，q2为空队；否则交换
        if (q1.empty()&&!q2.empty())
        {
            queue<T> tmp;
            tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        if (q1.size())
        {
            while (q1.size()!= 1)//q1为非空队，且最终q1只能保留一个元素，这个元素为栈顶元素
            {
                q2.push(q1.front());
                q1.pop();
            }
            q1.pop();
        }
    }
    size_t Size()
    {
        return q1.size() + q2.size();
    }
    bool Empty()
    {
        return (q1.empty()&&q2.empty());
    }
    T& Top()
    {
        //默认q1非空，q2为空
        if (q1.empty() && !q2.empty())
        {
            queue<T> tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        if (!q1.empty())
        {
            while (q1.size() != 1)//q1为非空队，且最终q1只能保留一个元素，这个元素为栈顶元素
            {
                q2.push(q1.front());
                q1.pop();
            }
            q2.push(q1.front());//
            T data = q1.front();
            q1.pop();//始终保持有个队列为空；
            return data;
        }
    }
protected:
    queue<T> q1;
    queue<T> q2;
};

---

---

三.实现一个栈Push（出栈）Pop（入栈）Min（返回最小值的操作）的时间复杂度为O(1)

思路：通过俩个站来实现，一个来辅助储存所有元素（popstack），一个用来实现筛选最小当前最小数（pushstack）

思路图：

代码实现：

template<class T>
class StackReturnMin
{
public:
    void Push(const T* a, const size_t& size)
    {
        T Min = a[0];
        for (size_t i = 0; i < size; i++)
        {
            popstack.push(a[i]);
            if(a[i] <= Min)
                pushstack.push(a[i]);
            else
                pushstack.push(pushstack.top());
            Min = pushstack.top();
        }
    }
    void Pop()
    {
        pushstack.pop();
        popstack.pop();
    }
    size_t Size()
    {
        return pushstack.size();
    }
    T& Top()
    {
        return pushstack.top();
    }
    bool Empty()
    {
        return pushstack.empty();
    }
protected:
    stack<T> pushstack;//出栈
    stack<T> popstack;//入栈
};