c - スタックをコピーするアルゴリズム

Question

外部スタックや配列を使用せずに、Cでスタックを別のスタックにコピーすることは可能ですか？

再帰を使用して実行できることは知っていますが、前述の制約内でこれを実行するための他の可能な解決策はありますか？

Answer 1

はい、可能ですが、時間がかかりO(N^2)ます。スタックS(ソース) とT(ターゲット) を検討してください。

1. countゼロに初期化
2. Eスタックから一番上の要素をポップしS、残りのデータをスタックにプッシュして、アイテムをスタックTに残しますcountS
3. E上に押し込むS
4. 要素をコピーして元にT戻すS
5. インクリメントcount
6. count が の項目数と等しくない場合は、S手順 1 に戻ります。
7. の要素をポップSしてプッシュするT

ステップ 0 から 5 までのリバース スタックSが所定の位置にある。ステップ 6 で に移動しT、順序を逆にして元のコピーを作成します。ただし、元のスタックが空になっているため、これは破壊的なコピーです。

Answer 2

あまり効率的ではありませんが、実行可能です。

Stack S = source, Stack T = target, int size = number of elements;
while(size >0 ) {
  pop size-1 elements from S (all but last), pushing them onto T (using it as temp storage)
  pop and copy the last element from S; push it back onto S;
  pop and push size-1 elements on T back to S.
  push your copy  of the last element onto T
  decrement size;
}

うごれんを引用すると、これは「2本のペグと一定数の1枚組の収納スペースがあるハノイの塔」に似ています。

Answer 3

わかりました、私自身のビジュアライゼーションと、あるスタックから別のスタックへの真の非破壊コピーのソリューションを紹介します。

スタックSとのペアがありT、次のように互いに向かって成長する様子を想像できます。

    ____________        _______________
    |                                  |
S   | S0 S1 S2   ........     T2 T1 T0 | T
    |____________       _______________| 

データ構造全体を単一のシーケンスと見なすと、特定の要素を位置から(S0, S1, S2, ...., T2, T1, T0)位置に移動またはコピーするアクションを実行できます。どうやってこれを行うのですか？このシーケンスは、次のように小さなステップで進むことができます。ij

void MoveLeft()
{
    T.push( S.pop() );
    curPosition--;
}

void MoveRight()
{
    S.push( T.pop() );
    curPosition++;
}

次に、任意の要素にアクセスして記憶し、別の位置に移動してその要素をそこに配置できます。ヘルパー関数は次のとおりです。

void MoveToI(int i)
{
    while( curPosition > i ) {
        MoveLeft();
    }

    while( curPosition < i ) {
        MoveRight();
    }
}

したがって、これらの操作を使用して、基本的にシーケンス(S0,S1,S2,...,SN)をに変換します(S0,S1,S2,...,SN,SN,SN-1,...,S2,S1,S0)。

そして、ここにアルゴリズムがあります：

curPosition = NElements;
for( int i = 0; i < NElements; ++i ) {
    MoveToI( i );
    x = T.peek();
    MoveToI(Nelements);
    T.push( x );
}

MoveToI( Nelements );