脑筋急转弯：如何用两个栈实现一个队列？用两个队列实现一个栈
怎么判断呢？谁的标兵为 0，谁就是存（刚起步的时候手动指定 A 的标兵为-1 嘛，第一个存进去的时候一次性加 2）
也省得倒腾来倒腾去。
如果两个队列都被清空了，我们就再次将标兵 A 置为-1，这样还能提高代码的复用性。
好，接下来我们看一下别人的。
02 别人的想法
========
两个栈实现一个队列？
==========
看到一个和我想法差不多的老哥啊，不过他考虑得好像没有我详细哈。
图（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);
}
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论