首先，我们得了解队列和栈的基本原理。
成都创新互联公司成立与2013年，先为黄山等服务建站，黄山等地企业，进行企业商务咨询服务。为黄山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
队列是一个“先进先出“的一个结构。队列的定义是在队尾插入，在队头删除，这就要求要用一种在尾部插入容易的，在头部删除容易的结构，你一定会想到单链表，对，库的实现就是用一个链表实现的。
栈，相信大家都不会陌生，函数栈帧等的实现，它是一种”先进后出“的结构。栈的插入删除都是在尾部进行的。
所以要用队列实现一个栈，要解决的问题就是在删除时要删除最后插入的那个元素。
我们先来模拟一下出栈和入栈的情况：
（1）入栈：Q1：1，2，3，4入队列（相当于入栈）；
（2）出栈：Q1：1，2，3出队列，Q2：1，2，3入队列；（此时Q1只剩4，正是我们要出栈的元素）
（3）
1>入栈：Q1：5入队列（每次入栈都用Q1入队列实现，而不入队列Q2，这样会提高效率，后面会说到）
2>出栈：判断：如果Q1队列不为空就用（1）（2）步的方法出栈最后一个元素。否则，出栈Q2队列的最后一个元素。
我们首先来搭建这个栈的结构：
#pragma once
#include
#include
#include
#include
using namespace std;
template
class MYStack
{
public:
MYStack()
:_size(0)
{
}
~MYStack()
{
}
void Push(const T& x);
void Pop();
bool Empty();
size_t Size();
void Print();
private:
queue q1;
queue q2;
size_t _size;
};
一个栈具有的功能我们都实现一下，Psh(),Pop(),Empty(),Size()等等。
在这个结构中数据成员是两个队列的对象，因为我们是用两个队列来实现的，还有一个_size用来记录栈中元素的个数。
下面是函数具体实现：
template
void MYStack::Push(const T& x)
{
q1.push(x);
++_size;
}
template
void MYStack::Pop()
{
//assert(_size > 0);
//size_t plen = q1.size();
//while (plen != 1)
//{
// T tmp = q1.front();
// q2.push(tmp);
// q1.pop();
// --plen;
//}
//q1.pop();
//plen = q2.size();
//while (plen)
//{
// T tmp = q2.front();
// q1.push(tmp);
// q2.pop();
// --plen;
//}
//--_size;
assert(_size > 0);
size_t plen = q1.size();
if (plen == 0)
{
//if (q2.size() == 0)
// return;
plen = q2.size();
while (plen != 1)
{
T tmp = q2.front();
q1.push(tmp);
q2.pop();
--plen;
}
q2.pop();
}
else
{
size_t plen = q1.size();
while (plen != 1)
{
T tmp = q1.front();
q2.push(tmp);
q1.pop();
--plen;
}
q1.pop();
}
--_size;
}
template
bool MYStack::Empty()
{
return _size ? false : true;
}
template
size_t MYStack::Size()
{
return _size;
}
template
void MYStack::Print()
{
//size_t plen = q1.size();
//while (plen--)
//{
// cout << q1.front() << " ";
// q1.pop();
//}
size_t plen = q2.size();
while (plen--)
{
cout << q2.front() << " ";
q2.pop();
}
plen = q1.size();
while (plen--)
{
cout << q1.front() << " ";
q1.pop();
}
}
注释掉的部分也可以实现，它的原理是不管第（3）步是出栈还是入栈，都把剩下的元素从Q2出栈入栈到Q1，输出的时候只用输出Q1中的元素。但是它的效率较低。如果有这种情况：1，2，3.....100000入栈，然后1，2，3......100000出栈，这会导致Q1和Q2频繁的出栈和入栈，效率非常之低。
优化方法就是没有注释部分。它的实现就是入栈都是Q1入队列，出栈后不把Q2的元素移到Q1，这样的话效率就会提高，只是在输出的时候要先输出Q2里的元素，再输出Q1里的元素。因为Q1里的元素总是栈顶的元素。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网页名称：使用两个队列实现一个栈-创新互联
转载注明：
http://bjjierui.cn/article/hjjhp.html
