【数据布局】栈口试题--两个栈实现一个行列
|
起首我们必需清晰，栈先辈后出，行列先辈先出。这道他们各自的特点往后，我们用两个栈来实现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点，可是都 可以实现。 假如以上论述有题目，可以提出~~~ （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
