@[toc]
前言
其实我也不知道这两个问题又什么意义，就像不知道我们平时刷的算法题除了练脑子还有啥意义。
那就练一下，我先说一下我的想法，但是我知道，我的观点写不了几个字，所以后面肯定要掺和一下别人的看法。
我的想法
如何用两个栈实现一个队列
我发四，我只是想找张图，没想到它把我想说的话说了一半掉了。
但是，我觉着它倒来倒去烦不烦呐？
首先，我们分栈A、栈B。
操作有插入，取出。
标兵有栈A标兵、栈B标兵，标记哪个栈为正在插入的栈，哪个栈为正在取出的栈。
刚开始肯定都是无状态的，这时候要取，什么也取不出来，得先存钱。
挑栈A为存、栈B自然为取。
存着存着，要取一个的时候，将栈A全部倒进栈B，栈该怎么出栈就是怎么出栈。栈B出栈一个。
每次出栈，都检查一下负责出栈的栈B是否为空了，空了就把A里面带的东西再都倒进来，如果没得倒，那就说明没东西了。
取完一个之后，想存就继续存，想取就继续取，悉听尊便。
==为什么取一下就要倒一波，累不累啊？==
如何用两个队列实现一个栈
这个就比较麻烦一些了。
上面那个想了一分钟，这个想了三分钟，我想来想去，两个队列怎么拼，它还是队列啊。
后面想了一下栈的操作，聪明花突然就开了。
首先，材料有两个队列、两个标兵。
刚开始，队列都是空的，只能存，不能取。
存的时候，先往队列A里面存，标兵纪录队列长度。
存到不想存了，想取了，怎么操作？依次出队，往队列B里面去，标兵AB同时工作，纪录各自队列长度。
当队列A只有一个元素的时候，出队。
这时候，存取关系就变了，队列B变为了存队列，队列A变为了取队列。
怎么判断呢？谁的标兵为0，谁就是存（刚起步的时候手动指定A的标兵为-1嘛，第一个存进去的时候一次性加2）
也省的倒腾来倒腾去。
如果两个队列都被清空了，我们就再次将标兵A置为-1，这样还能提高代码的复用性。
好，接下来我们看一下别人的。
别人的想法
去取取经。
来自：https://blog.csdn.net/cherrydreamsover/article/details/80466781
两个栈实现一个队列
看到一个和我想法差不多的老哥啊，不过他考虑的好像没有我详细哈。
图（1）：将队列中的元素“abcd”压入stack1中，此时stack2为空；
图（2）：将stack1中的元素pop进stack2中，此时pop一下stack2中的元素，就可以达到和队列删除数据一样的顺序了；
图（3）：可能有些人很疑惑，就像图3，当stack2只pop了一个元素a时，satck1中可能还会插入元素e,这时如果将stack1中的元素e插入stack2中，在a之后出栈的元素就是e了，显然，这样想是不对的，我们必须规定当stack2中的元素pop完之后，也就是satck2为空时，再插入stack1中的元素。
代码实现：
template<typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T>
void CQueue<T>::appendTail(const& T& element)//尾插
{
stack1.push(element);
}
template<typename T>
T CQueue<T>::deleteHead()
{
if (stack2.size() <= 0)
{
while (stack1.size > 0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
T head = stack2.top();
stack2.pop();
if (stack2.size() == 0)//当stack2为空时，抛异常
throw new exception("queue is empty");
return head;
}
如何用两个队列实现一个栈
还是那句话，没有我细嘿嘿
图（1）：当栈里面插入元素“abcd”的时候，元素a在栈底（最后出去），d在栈顶（最先出去）；
图（2）：将元素“abc”从q1中头删，然后再q2中尾插进来之后，头删q1中的元素“d”，就相当于实现了栈顶元素的出栈；
图（3）：同理，将元素“ab”从q2中头删，然后尾插到q1中，然后再头删q2中的元素“c”;
图（4）：同理，删除元素“b”;
图（5）：当栈又插入一个元素“e”时，此时元素“a”不能从队列中删除，而是将元素“a”插入q2中，再删除q1中的元素“e”,最后再删除元素“a”。
说明：其中红色框代表该队列中的元素出队列，该队列为空。
代码实现：
template<typename T> class CStack
{
public:
CStack(void);
~CStack(void);
void appendTail(const T& node);
T deleteHead();
private:
queue<T> q1;
queue<T> q2;
};
template<typename T>
void CStack<T>::appendTail(const T& node)//实现栈元素的插入
{
//数据的插入原则：保持一个队列为空，一个队列不为空，往不为空的队列中插入元素
if (!q1.empty())
{
q1.push(node);
}
else
{
q2.push(node);
}
}
template<typename T>
T CStack<T>::deleteHead()//实现栈元素的删除
{
int ret = 0;
if (!q1.empty())
{
int num = q1.size();
while (num > 1)
{
q2.push(q1.front());
q1.pop();
--num;
}
ret = q1.front();
q1.pop();
}
else
{
int num = q2.size();
while (num > 1)
{
q1.push(q2.front());
q2.pop();
--num;
}
ret = q2.front();
q2.pop();
}
return ret;
}