是否可以检查存储在堆栈中的单词是否是回文，而无需 C++ 中的任何附加数据结构

Question

在C++程序中，我们来分析一下栈的数据结构。我的问题是：是否可以在没有任何额外数据结构且不修改堆栈的情况下检查给定堆栈是否包含回文？只要您将堆栈重新组合在一起（我的意思是通过修改），您就可以分解堆栈。

示例 1：s = {1, 2, 3, 2, 1} - 它是回文示例 2：s = {1, 2, 3, 4, 5} - 它不是回文

我唯一的想法是用递归来做:

void checkStack(Stack<int>& s){
    //Exit condition
    if(s.numberOfElements() == 0){
        return;
    } 

    int temp = s.pop(); 

    checkStack(s);

    s.push(temp); 
}

Answer 1

Is it possible to check if word stored on stack is palyndrome without ANY additonal data structures in C++

我认为你所说的数据结构是指一些其他抽象数据结构或容器，如列表、向量等。

您可以通过将标准 class std::stack<int>.

封装在包装器中来完成您的任务

例如

#include <iostream>
#include <iomanip>
#include <stack>
#include <iterator>
#include <algorithm>

bool is_palindrome( const std::stack<int> &st )
{
    struct wrapper : std::stack<int>
    {
        wrapper( const std::stack<int> &st ) : std::stack<int>( st ) {}

        bool is_palindrome() const
        {
            return std::equal( std::begin( c ), std::next( std::begin( c ), c.size() / 2 ),
                               std::rbegin( c ) );
        }
    } w( st );


    return w.is_palindrome();
}

int main() 
{
    std::stack<int> st1( std::stack<int>::container_type{ 1, 2, 3, 2, 1  } );

    std::cout << std::boolalpha << is_palindrome( st1 ) << '\n';

    std::stack<int> st2( std::stack<int>::container_type{ 1, 2, 3, 4, 5  } );

    std::cout << std::boolalpha << is_palindrome( st2 ) << '\n';

    return 0;
}

程序输出为

true
false

class wrapper 可以访问 class std::stack<int> 的受保护数据成员 c，表示底层容器。

Answer 2

老实说，我很确定您没有完全正确地引用任务描述。该任务有几处可疑...

首先，有人可能会吹毛求疵，认为不使用任何其他数据结构就不可能使用 std::stack。 std::stack 只是一个容器适配器，它建立在一些底层容器之上。默认值为 std::deque。严格来说，使用 std::stack 而不使用任何其他数据结构是没有意义的。

接下来不允许修改堆栈，但是可以分解，只要重新组合起来即可。这基本上允许你做任何事情。我的意思是，例如，您可以编写一个 returns 您第 n 个元素的函数，例如：

int access(std::stack<int> s, size_t i) {
    while (i--) s.pop();
    return s.top();
}

使用它编写回文测试有点简单。然而，这基本上是将堆栈视为不是堆栈。对于绕过 std::stack 的堆叠的类似方法，请参阅。

请注意，对于上面的小作弊，我必须复制堆栈（s 是按值传递的），我无法想象一个至少不会使用的解决方案，即使是递归的解决方案第二个堆栈。当你分解堆栈时，你需要将元素存储在某个地方，否则之后你将如何恢复它？

让我们暂时忘记确切的任务，考虑如何检查 std::stack 是否包含回文（没有不明确的约束），那么一个简单的解决方案是

bool check_palindrome(std::stack<int>& s) {
    std::stack<int> t;
    while (t.size() < s.size()) {
        auto temp = s.top();
        s.pop();
        t.push(temp);
    }
    if (t.size() > s.size()) t.pop();
    return s==t;
}

这也可以变成递归方法（老实说，我不太了解递归的炒作），但如果没有第二个堆栈，我不知道该怎么做。我也懒得重建原始堆栈，但这样做很容易。

是否可以检查存储在堆栈中的单词是否是回文，而无需 C++ 中的任何附加数据结构

Is it possible to check if word stored on stack is palyndrome without ANY additonal data structures in C++

c++

algorithm

stack

palindrome