1

假设我们在 c++ 中，使用 STL Stack 和 Queue

    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

不需要递归，这将是对资源的无用浪费。无需改变你的queueand stack（换句话说，这甚至适用于const's ）。

假设您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现在，如果您使用不同的容器类型作为and的底层实现stack，您仍然可以使用相同getContainer()的技术来获取按相同顺序排序的容器：两者queue::push()并stack::push()调用底层容器的push_back()方法，只有当您pop()（和类似操作）反转发生在stack. 由于这些底层容器的顺序相同，因此您可以更轻松地进行比较（留给读者作为练习；））。

信用：我懒得重新实现一个受保护的成员访问器，所以我无耻地复制和修改了这个。

于 2013-03-02T17:38:04.340 回答
0

部分递归的解决方案是递归地将队列中的所有元素弹出到辅助堆栈中，然后检查辅助堆栈和原始堆栈是否相同。这种检查也可以递归地进行。

于 2013-03-02T17:18:09.263 回答
0

你可能不会同时弹出它们，你可以尝试弹出一个（使用记录它的东西）ADT（不要弹出队列，弹出堆栈），然后到基数（大小==1），然后你比较并对队列进行一些更改, 并返回。然后在每次递归调用后对记录器和当前队列的前面做一些事情，你会找到答案。

于 2014-03-01T07:01:04.450 回答