是否可以检查存储在堆栈上的单词是否是回文，而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

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

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

您可以通过将标准类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

类wrapper有权访问表示基础容器的类std::stack<int>的受保护数据成员c。

Answer 2

老实说，我很确定你引用的任务描述并不完全正确。这项任务有几件事很可疑...

首先，人们可以做一些头发分裂，并争辩说，如果不使用任何其他数据结构，就不可能使用std::stack。std::stack只是基于某个基础容器构建的容器适配器。默认值为std::deque。严格来说，使用std::stack而不使用任何其他数据结构是没有意义的。

接下来，不允许修改堆栈，但可以分解它，只要您再次将其重新组合在一起即可。这基本上允许您做任何事情。我的意思是，例如，您可以编写一个返回第 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;
}

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