【数据结构】栈面试题--两个栈实现一个队列
栏目：php教程时间：2016-12-12 15:49:05
首先我们必须清楚，栈先进后出，队列先进先出。这道他们各自的特点以后，我们用两个栈来实现1个队列。
下边给出图片：
下边给出代码：
template<typename T>
class Queue
{
public:
void Push(const T& x)
{
if (!_s2.empty())
{
while (!_s2.empty())
{
_s1.push(_s2.top());
_s2.pop();
}
}
_s1.push(x);
}
void Pop()
{
if (_s1.empty() && _s2.empty())//s1,s2均为空
{
return;
}
if (!_s2.empty())//s2不为空
{
_s2.pop();
}
if (!_s1.empty() && _s2.empty())//s1不为空
{
//while(!_s1.empty())
while (_s1.size() != 1)
{
_s2.push(_s1.top());//可以少push1次
_s1.pop();
}
_s1.pop();
}
}
void Display()
{
while (!_s2.empty())
{
cout << _s2.top() << " ";
_s2.pop();
}
while (!_s1.empty())
{
_s2.push(_s1.top());
_s1.pop();
}
while (!_s2.empty())
{
cout << _s2.top() << " ";
_s2.pop();
}
}
int Size()
{
return _s1.size() + _s2.size();
}
public:
stack<T> _s1;
stack<T> _s2;
};
void test()
{
Queue<int> q;
cout << q.Size() << endl;
q.Push(2);
q.Push(3);
q.Push(1);
q.Pop();
q.Push(4);
q.Push(5);
q.Pop();
cout << q.Size() << endl;
q.Display();
}
int main()
{
test();
system("pause");
return 0;
}
以上代码的实现方法是图片右下角的解决方案所述（即就是：push时，如果栈2不为空，将栈2的元素push进栈1，
然后，直接将新的元素push进栈1；如果栈2为空，直接push进栈1 pop时，当栈2不为空，直接从栈2pop；当栈
2为空，将栈1的元素push进栈2（可以少push1次），弹出栈顶元素）
下边再给出另外1种实现办法（即就是1次pop以后，栈2的元素都push进栈1，具体思路图片中并没有提出）：
看下边的代码（仅仅给出pop和push函数，其他的函数都同上）
void Push(const T& x)
{
_s1.push(x);
}
void Pop()
{
if (_s1.empty() && _s2.empty())//s1,s2均为空
{
return;
}
if (!_s2.empty())//s2不为空
{
_s2.pop();
}
else if (!_s1.empty() && _s2.empty())//s1不为空
{
//while(!_s1.empty())
while (_s1.size() != 1)
{
_s2.push(_s1.top());//可以少push1次
_s1.pop();
}
_s1.pop();
}
while (!_s2.empty())
{
_s1.push(_s2.top());
_s2.pop();
}
}
上边代码就实现了每次pop完以后，都将栈2中的剩余元素push进栈1，这类方法可能较第1种方法麻烦1点，但是都
可以实现。
如果以上叙述有问题，可以提出~~~
------分隔线----------------------------
------分隔线----------------------------