014ライタはスタックを昇順に並べ替えて、このスタックがどのように実現されているのか、特別な仮定をするべきではありません(keep it up)
ライトプログラムはスタックを昇順に並べ替えます.このスタックがどのように実現されているかについては、特別な仮定をするべきではありません.
プログラムで使用できるスタック操作は、push|pop|isEmpty
一番考えやすいのは優先キューでこの問題をして、実現しやすいことです.
さらに、スタックの昇順配列を実現するために、スタックをもう1つ使用することができます.
優先キュー:
追加のスタックで実装:
第2のアルゴリズムには極端なテスト列があります.元のスタックのデータの下部から上部までが小さい場合、例えば:
1 2 3 4 5 6 7
Tmpはpushのたびに異なる数でスタック内のすべてのデータを空にします.例えば、ある時点で
vStk:1 2 3 4 5
Tmp:6 7
Tmpがpush 5を必要とする場合は6 7を空にし、push 5でvStkスタックのデータが増加します.
vStk: 1 2 3 4 7 6
Tmp: 5
プログラムで使用できるスタック操作は、push|pop|isEmpty
一番考えやすいのは優先キューでこの問題をして、実現しやすいことです.
さらに、スタックの昇順配列を実現するために、スタックをもう1つ使用することができます.
優先キュー:
//
void sortStack(std::stack<int>& vStk)
{
std::priority_queue<int, std::vector<int>, std::greater<int>> Queue;
while (!vStk.empty())
{
Queue.push(vStk.top());
vStk.pop();
}
while (!Queue.empty())
{
vStk.push(Queue.top());
Queue.pop();
}
}
追加のスタックで実装:
//
void sortStack_(std::stack<int>& vStk)
{
std::stack<int> Tmp;
while (!vStk.empty())
{
int Top = vStk.top();
vStk.pop();
while (!Tmp.top() && Top < Tmp.top())
{
vStk.push(Tmp.top());
Tmp.pop();
}
Tmp.push(Top);
}
}
第2のアルゴリズムには極端なテスト列があります.元のスタックのデータの下部から上部までが小さい場合、例えば:
1 2 3 4 5 6 7
Tmpはpushのたびに異なる数でスタック内のすべてのデータを空にします.例えば、ある時点で
vStk:1 2 3 4 5
Tmp:6 7
Tmpがpush 5を必要とする場合は6 7を空にし、push 5でvStkスタックのデータが増加します.
vStk: 1 2 3 4 7 6
Tmp: 5