Check if a stack is palindrome

Question

In a recent coding interview I was asked to solve a problem in which the task was to complete a function which receives a stack as an argument by reference and checks if the passed stack is palindrome or not. I did come up with an approach but it's not at all a good approach according to me.

My Code

#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;
} 

Is there a better way to do this? I am preferably looking for a recursive algorithm/code.

Answer 1

One approach to this would be to pop half of the stack, push onto another stack and compare them. For example:

   [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

Only if the stack size is odd, we must pop the center of the palindrome (C) as the final step.

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

If the state of the original stack should be restored, we simply need to reverse the process by popping from our tmp stack and pushing back onto the input stack. Keep in mind that we then don't discard the middle element, but store it temporarily before pushing it back again.

Or, if this is not considered "cheating", we could simply accept stack as a value instead of an lvalue-reference. Then we just copy it before making any changes.

Alternative Recursive Implementation

// 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

I don't think you need a recursive algorithm here, just push half the elements from the stack onto a second stack then pop elements of both stacks and check they're the same:

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

Answer 3

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