2013-03-02 120 views
0

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

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

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

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

+3

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

+0

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

+0

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

回答

0

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

+0

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

0

不需要递归,这将是无用的资源浪费。不需要改变你的queuestack(换句话说,即使在const上也可以)。

假设你std::stackstd::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; 
} 

现在,如果你用不同的容器类型为queuestack底层实现,你仍然可以使用相同的getContainer()技术获得是sorte容器d以相同的顺序:queue::push()stack::push()调用底层容器的方法push_back(),它只有当您pop()(和类似的操作)的逆转发生在stack。由于这些底层容器的排列顺序相同,因此您可以更轻松地进行比较(作为练习留给读者;))。

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

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; 
} 
+0

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

0

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