Is there a good way to determine if a stack is a palindrome?

Since palimdrome stacks are by definition symmetric, you can cut the stack in half, reverse the second half, and compare it to the unaltered first half. This is the fastest possible strategy to do this. Speeding it up any further would require faster hardware. When you compare the entire stack, you waste half of your time, since all combinations in the last half have already been checked in the first half.

@PhiNotPi how do you “cut it in half” when you don’t know the length/size?

@phaedyryx He might be right in that doing a linear computation of length and then another linear comparison of length/2 is better.

Most stacks store their elements in either arrays or linked lists which means they should also be keeping track of the number of elements. It’s weird that the stack you’re using doesn’t include the length. All the modern languages that I’ve used (Java, C#, PHP, Python) contain this stack functionality.

If the stack really doesn’t maintain a count though, you could write a simple wrapper class around a stack object that would keep track of the pushed elements in a member variable and return it when asked. It might look like this C# example:

public class CountingStack<Type> {
  private int m_iCount;
  private Stack m_stStack<Type>;
  
  public CountingStack { m_iCount = 0; m_stStack = new Stack<Type>(); }
  public void Push(Type tNewElement) { m_stStack.Push(tNewElement); m_iCount ++; }
  public Type Pop() { m_iCount – -; return m_stStack.Pop(); }
  public int Count {
    get { return m_iCount; }
  }
}

At that point it’s just a matter of popping off and saving the first half of the stack and comparing it to the second half as you continue to pop – a linear complexity, O(n) algorithm that can be done in one for loop.