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.

Jan Schultke · Accepted Answer · 2020-08-31T06:53:21.977

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

score 3 · Answer 2 · edited Aug 30 '20 at 20:45

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

edited Aug 30 '20 at 20:45

Bill Lynch

80,138
16
128
173

answered Aug 30 '20 at 20:26

asmmo

6,922
1
11
25

This solution appears to alter the contents of the original stack, which may or may not be prohibited. – Sam Varshavchik Aug 30 '20 at 20:28
@SamVarshavchik the op said by reference, not by const reference. the op can take a copy if the stack is wanted to be const – asmmo Aug 30 '20 at 20:30
In the question itself, the original contents of the stack were restored, after the work was done. It may or may not be a requirement that the stack is modifiable, but its contents should be left along, after the work is done. – Sam Varshavchik Aug 30 '20 at 20:31

Alan Birtles · Answer 3 · 2020-08-30T20:47:09.477

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

Check if a stack is palindrome

My Code

3 Answers3

Alternative Recursive Implementation