检查堆栈是否为回文

Question

在最近的编码面试中，我被要求解决一个问题，其中的任务是完成一个函数，该函数通过引用接收堆栈作为参数，并检查传递的堆栈是否为回文。我确实想出了一个方法，但根据我的说法，这根本不是一个好方法。

我的代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void copy_it(stack<int> &st, stack<int> &temp) {
    if(st.empty())
        return;
    int element = st.top();
    temp.push(element);
    st.pop();
    copy_it(st, temp);
    st.push(element);
}
bool check_palindrome(stack<int> &st, stack<int> &temp) {
    if(st.size() != temp.size())
        return false;
    while(!st.empty()) {
        if(st.top() != temp.top())
            return false;
        st.pop();
        temp.pop();
    }
    return true;
}
int main()
{
    vector<int>vec{-1, -2, -3, -3, -2, -1};
    stack<int>st;
    for(int i = vec.size() - 1; i >= 0; --i) {
        st.push(vec[i]);
    }
    stack<int> temp;
    copy_it(st, temp);
    cout << check_palindrome(st, temp);
   return 0;
}

有更好的方法吗？我最好寻找递归 algorithm/code.

Answer 1

一种方法是弹出堆栈的一半，压入另一个堆栈并比较它们。例如：

   [A, B, C, B, A]       // our stack, where right is top
-> [A, B, C, B], [A]     // pop A, push A onto temporary stack
-> [A, B, C], [A, B]     // pop B, push B
-> [A, B], [A, B]        // pop C, discard C

只有当堆栈大小为奇数时，我们才必须弹出回文的中心（C）作为最后一步。

bool isPalindrome(std::stack<int> &stack) {
    std::stack<int> tmp;
    size_t size = stack.size();
    size_t halfSize = size / 2;
    for (size_t i = 0; i < halfSize; ++i) {
        tmp.push(stack.top());
        stack.pop();
    }
    // discard leftover element if the number of original elements is odd
    if (size & 1) {
        stack.pop();
    }
    return tmp == s;
}

如果要恢复原始堆栈的状态，我们只需要通过从 tmp 堆栈中弹出并推回输入 stack 来反转该过程。请记住，我们不会丢弃中间元素，而是在再次将其推回之前暂时存储它。

或者，如果这不被视为“作弊”，我们可以简单地接受 stack 作为值而不是 lvalue-reference。然后我们在进行任何更改之前复制它。

替代递归实现

// balance() does the job of popping from one stack and pushing onto
// another, but recursively.
// For simplicity, it assumes that a has more elements than b.
void balance(std::stack<int> &a, std::stack<int> &b) {
    if (a.size() == b.size()) {
        return;
    }
    if (a.size() > b.size()) {
        b.push(a.top());
        a.pop(); 
        if (a.size() < b.size()) {
            // we have pushed the middle element onto b now
            b.pop();
            return;
        }
    }
    return balance(a, b);
}

bool isPalindrome(std::stack<int> &stack) {
    std::stack<int> tmp;
    balance(stack, tmp);
    return stack == tmp;
}

Answer 2

bool check_palindrome(std::stack<int> &st) {
    std::stack<int> temp;
    auto initialSize = st.size();
    for(size_t i{}; i < initialSize/2; ++i) { temp.push(st.top()); st.pop(); }
    if(temp.size() < st.size()) st.pop();
    return st == temp;
}

Answer 3

我认为这里不需要递归算法，只需将堆栈中的一半元素压入第二个堆栈，然后弹出两个堆栈的元素并检查它们是否相同：

int main()
{
    vector<int>vec{-1, -2, -3, -3, -2, -1};
    stack<int>st;
    for(int i = vec.size() - 1; i >= 0; --i) {
        st.push(vec[i]);
    }
    stack<int> temp;
    for (size_t i = 0; i < st.size() / 2; i++)
    {
      temp.push(st.top());
      st.pop();
    }
    if (st.size() != temp.size()) st.pop();
    while (!st.empty())
    {
      if (st.top() != temp.top()) return 1;
      st.pop();
      temp.pop();
    }
    return 0;
}

检查堆栈是否为回文

Check if a stack is palindrome

c++

algorithm

stack

palindrome

stdstack

我的代码

替代递归实现