比较队列和堆栈的内容

假设我们在C++中，使用STL栈和队列比较队列和堆栈的内容

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

什么是最优雅的方式来递归地检查数据项是相同的内容和顺序方面？假设上面显示的堆栈和队列具有相同的数据和相同的顺序。

我在概念上理解问题，因为数据弹出（）以相反的顺序来做什么。

来源

2013-03-02 herpderp

[Whathaveyoutried]（http://mattgemmell.com/2008/12/08/what-have-you-tried/）？为什么你需要递归检查？ – Byron 2013-03-02 17:10:38

我不能在概念上设想一种方法来做到这一点，所以我没有尝试过任何东西。但是，我发现我可以根据STL队列查看队列的前面和后面。我认为这有助于。 – herpderp 2013-03-02 17:32:43

你确定这不是[课堂]（https://wiki.engr.illinois.edu/display/cs225sp11/Lab06）吗？特别是因为它似乎大约在同一时间。这可能被认为是作弊 – asymptotically 2013-08-13 19:26:50

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

来源

2013-03-02 17:18:09 niculare

这是非常真实的;似乎认为有一种方法可以不创建新的队列或堆栈。 – herpderp 2013-03-02 17:39:33

不需要递归，这将是无用的资源浪费。不需要改变你的queue和stack（换句话说，即使在const上也可以）。

假设你std::stack和std::queue在内部使用相同类型的基础容器（这应该是std::dequeue如果使用默认值），那么你可以访问两个queue的保护成员c（你的真实容器）和stack并加以比较利用运营商==：

#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()技术获得是sorte容器d以相同的顺序：queue::push()和stack::push()调用底层容器的方法push_back()，它只有当您pop()（和类似的操作）的逆转发生在stack。由于这些底层容器的排列顺序相同，因此您可以更轻松地进行比较（作为练习留给读者;））。

来源：我懒得再次实现一个受保护的成员accessor，于是我无耻地复制和修改了this one。

来源

2013-03-02 17:38:04 syam

如果通过递归，你不是指递归函数调用，而只是循环，那么这里是一个答案。该函数首先检查堆栈和队列是否大小相同。如果它们的大小不一样，则该函数返回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-02 17:58:52 CodeBricks

这可行，但这是很多副本。根据容器的实际大小，这可能是一个问题。 – syam 2013-03-02 18:05:24

U可以不同时弹出他们，ü可以尝试弹出一个（使用的东西记录吧）ADT（不弹出队列，POP堆栈），并且在底座（大小== 1），和u比较并对队列进行了一些更改并返回。然后在每次递归调用之后用记录器和当前队列的前端做一些事情，你会找到答案。

来源

2014-03-01 07:01:04

比较队列和堆栈的内容

回答

相关问题