【数据结构】栈面试题--两个栈实现一个队列
|
首先我们必须清楚，栈先进后出，队列先进先出。这道他们各自的特点以后，我们用两个栈来实现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点，但是都 可以实现。 如果以上叙述有问题，可以提出~~~ （编辑：淮安站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
