【デッドロックアルゴリズム・スタックとキュー】デュアルスタック並べ替え問題

1445 ワード

タイトルの要求:1つのスタックの要素のタイプは整数型で、今このスタックを最上位から小ソート(vectorの最初の要素はスタックの最上位)にしたいのですが、1つのスタックしか申請できません.それ以外に新しい変数を申請することができますが、追加のデータ構造を申請することはできません.どのようにソートを完了しますか?
構想:元のスタックをstackとし、申請した補助スタックをhelpとし、helpをトップダウンから小から大へ並べ替えると、helpをstackに注ぎ込み、stackトップダウンから大から小へ並べ替えることができる.
スタックトップ要素をstackからポップアップし、currentとしてマークします.
currentがhelpに等しいスタックトップ要素より小さい場合、currentはhelpに押し込まれます.
currentがhelpのスタックトップ要素より大きい場合は、currentがhelpのスタックトップ要素以下になるまで、helpの要素をstackにポップアップします.
stackの要素がすべてhelpに移行するまで、helpのスタック要素をstackに1つずつ押し返せばよい.
この問題はvectorでstackを実現する、vectorの最初の要素がスタックトップである、戻るvectorにおいてvector[0]が最大値である、出願の補助vectorにおいてvector[0]が最小値であるべきである.
だからhelpベクトルでvector[0]...vector[length-1]を小さいものから大きいものに並べ替える.
numbersベクトルのnumbers[0]...numbers[lenght-1]を大きくから小さく並べ替えます.

class TwoStacks {
public:// vector     
    vector twoStacksSort(vector numbers) {
        // write code here
        vector help;
        while(!numbers.empty()){
             int current = numbers.back();
             numbers.pop_back();
             if(help.empty())
                 help.push_back(current);
             else{
                 if(current>=help.back())
                     help.push_back(current);
                 else{
                     while(!help.empty()&& current

Javascript設計モード-テンプレートメソッドモード

Dinicアルゴリズム(洛谷P 2763)