1

C++ で STL スタックとキューを使用しているとします。

    Stack:      [1 2 3 4 5] <=>
    Queue:   => [5 4 3 2 1] =>

データエントリの内容と順序が同じであることを再帰的に確認する最もエレガントな方法は何ですか? 上記のスタックとキューが同じデータと同じ順序を持っているとします。

データ pop() が逆の順序であるため、何をすべきかを概念的に理解するのに問題があります。

4

4 に答える 4

0

再帰とは、再帰関数呼び出しを意味するのではなく、単にループすることを意味する場合、ここに答えがあります。この関数は、最初にスタックとキューが同じサイズかどうかをチェックします。それらが同じサイズでない場合、関数は false を返します。この関数には、スタック パラメータの要素を取得するローカル スタック オブジェクトがあり、渡されたスタック パラメータとは逆の順序でポップされます。次に、スタックとキューの各フロント/トップ要素が等しいかループがチェックされます。等しい場合、ループは次の繰り返しに進みます。等しくない場合、関数は false を返します。false を返さずにループが終了した場合、関数は true を返します。

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

bool check(stack<int> stackPar, queue<int> queuePar)
{

    if (stackPar.size() != queuePar.size())
    {
        return false;
    }

    stack<int> reverseStack;

    for (int i = 0, initialSize = stackPar.size(); i < initialSize; ++i)
    {
        reverseStack.push(stackPar.top());
        stackPar.pop();
    }

    for (int i = 0; i < reverseStack.size(); ++i)
    {
        if (reverseStack.top() == queuePar.front())
        {
            reverseStack.pop();
            queuePar.pop();
        }
        else
        {
            return false;
        }
    }
    return true;
}

int main()
{
    stack<int> myStack;
    queue<int> myQueue;

    for(int i = 1; i <= 5; ++i)
    {
        myStack.push(i);
        myQueue.push(i);
    }

    cout << "Stack and queue are ";
    cout << ( check(myStack, myQueue) ? "equal." : "not equal." ) << endl;
    return 0;
}
于 2013-03-02T17:58:52.800 に答える
0

部分的に再帰的な解決策は、補助スタックのキューからすべての要素を再帰的にポップし、補助スタックと元のスタックが同じかどうかを確認することです。このチェックは再帰的に行うこともできます。

于 2013-03-02T17:18:09.263 に答える
0

U はそれらを同時にポップすることはできません。1 つをポップすることを試みることができます (何かを使用して記録します) ADT (ポップ キュー、ポップ スタックを使用しないでください)、およびベース (サイズ ==1) に対して、比較し、キューにいくつかの変更を加えます。 、および戻ります。次に、再帰呼び出しのたびにレコーダーと現在のキューのフロントで何かをすると、答えが見つかります。

于 2014-03-01T07:01:04.450 に答える
0

再帰は必要ありません。これは無駄なリソースの浪費になります。あなたのqueueandstackどちらかを変更する必要はありません (つまり、これはconstの上でも機能します)。

std::stackあなたと両方が内部的に同じタイプの基礎となるコンテナーを使用すると仮定すると (デフォルトを使用した場合std::queueはそうなるはずです)、両方の保護されたメンバー (実際のコンテナー) にアクセスし、 operator を使用してそれらを比較できます。std::dequeuecqueuestack==

#include <iostream>
#include <queue>
#include <stack>

template<typename Adapter>
typename Adapter::container_type const& getContainer(const Adapter& adapter) {
  struct AccessProtected : private Adapter {
    static typename Adapter::container_type const& getContainer(const Adapter& adapter) { return adapter.*&AccessProtected::c; }
  };
  return AccessProtected::getContainer(adapter);
}

int main() {
  std::queue<int> queue;
  std::stack<int> stack;
  for (int i = 0; i < 10; ++i) {
    queue.push(i);
    stack.push(i);
  }
  std::cout << (getContainer(queue) == getContainer(stack) ? "equal" : "not equal") << std::endl;
  return 0;
}

queueここで、との基になる実装として異なるコンテナー タイプを使用する場合でも、stack同じgetContainer()手法を使用して、同じ順序で並べ替えられたコンテナーを取得queue::push()できますstack::push()。の逆転が起こること。これらの基礎となるコンテナーは同じ順序になるため、物事をより簡単に比較できます (読者への演習として残しておきます ;))。push_back()pop()stack

クレジット:保護されたメンバー アクセサーを再実装するのが面倒だったので、恥知らずにこれをコピーして変更しました。

于 2013-03-02T17:38:04.340 に答える