Double Stack template

I decided to show a template form of my previous DoubleStack class so it is not just for ints.

template <typename T>
class DoubleStack
{
    int m_nTopA, m_nTopB, m_nSize;
    int *theStack;

public:
    DoubleStack(int nSize);
    ~DoubleStack(void)
    {
        if (theStack)
            delete theStack;
    }
  
    bool pushA(const T value);
    bool pushB(const T value);
    bool popA(T &value);
    bool popB(T &value);

    bool isFull()
    {
        if (m_nTopA+1 >= m_nTopB)
            return true;
        if (m_nTopB-1 <= m_nTopA)
            return true;
      
        return false;
    }
    bool isAEmpty(){return ((m_nTopA == -1) ? true : false);}
    bool isBEmpty(){return ((m_nTopB == m_nSize) ? true : false);}
};

template <typename T>
DoubleStack<T>::DoubleStack(int nSize)
{
    theStack = NULL;
    m_nSize = nSize;
    m_nTopA = -1;
    m_nTopB = nSize;
    if (m_nSize < 1)
        throw "Stack size must be greater than zero!";
    else
    {
        theStack = new T(m_nSize);
        if (!theStack)
            throw "Error creating the stack!";
    }
}

template<typename T>
bool DoubleStack<T>::pushA(const T value)
{
    if (isFull())
        return false;

    theStack[++m_nTopA] = value;
    return true;
}

template<typename T>
bool DoubleStack<T>::pushB(const T value)
{
    if (isFull())
        return false;

    theStack[--m_nTopB] = value;

    return true;
}

template<typename T>
bool DoubleStack<T>::popA(T &value)
{
    if (isAEmpty())
        return false;

    value = theStack[m_nTopA--];
    return true;
}

template<typename T>
bool DoubleStack<T>::popB(T &value)
{
    if (isBEmpty())
        return false;

    value = theStack[m_nTopB++];
    return true;
}

Double Stack

Here is another interesting problem I was given recently.  No, it's not a fast food burger, it's 2 stacks implemented using one array.  I created a class with the usual stack methods, but since this is a double stack we need to be able to push/pop onto/from both stacks.  We need to know the top positions of each stack and the size of the stack.  We also need to know when the stacks are empty and if there is room to add onto one of the stacks.


// class that defines a double stack
class DoubleStack
{
    int m_nTopA, m_nTopB, m_nSize;
    int *theStack;

public:
    DoubleStack(int nSize);
    ~DoubleStack(void);
   
    bool pushA(const int value);
    bool pushB(const int value);
    bool popA(int &value);
    bool popB(int &value);

    bool isFull();
    bool isAEmpty();
    bool isBEmpty();
};

Now that we have the class definition we'll have to implement it.  In the constructor we'll need to make sure we've recieved a valid size.  The stack will need to be at least one element long.  One element doesn't immediately sound like you would have a "double stack", but it is still possible.  We throw a general error message if the size is less than one or if there was a problem creating the array.  We'll initialize the top of stack A to be -1 and the top of stack B to the size of the array since both are empty.

DoubleStack::DoubleStack(int nSize)
{
    theStack = NULL;
    m_nSize = nSize;
    m_nTopA = -1;
    m_nTopB = nSize;
    if (m_nSize < 1)
        throw "Stack size must be greater than zero!";
    else
    {
        theStack = new int(m_nSize);
        if (!theStack)
            throw "Error creating the stack!";
    }
}

DoubleStack::~DoubleStack(void)
{
    if (theStack)
        delete theStack;
}

When pushing onto a stack we'll need to make sure that there is room to do the pushing.
 
bool DoubleStack::pushA(const int value)
{
    if (isFull())
        return false;

    theStack[++m_nTopA] = value;
    return true;
}

bool DoubleStack::pushB(const int value)
{
    if (isFull())
        return false;

    theStack[--m_nTopB] = value;
    return true;
}



When popping we'll need to make sure there are elements to pop.

bool DoubleStack::popA(int &value)
{
    if (isAEmpty())
        return false;

    value = theStack[m_nTopA--];
    return true;
}

bool DoubleStack::popB(int &value)
{
    if (isBEmpty())
        return false;

    value = theStack[m_nTopB++];
    return true;
}
 
Here we check to see if adding an element to the top of either stack will cause an overlap into the other stack.

bool DoubleStack::isFull()
{
    if (m_nTopA+1 >= m_nTopB)
        return true;
    if (m_nTopB-1 <= m_nTopA)
        return true;
   
    return false;
}

Check for empty stack methods are here.

bool DoubleStack::isAEmpty()
{
    return ((m_nTopA == -1) ? true : false);
}

bool DoubleStack::isBEmpty()
{    return ((m_nTopB == m_nSize) ? true : false);}

Bit Counting

I encountered a problem recently where I was asked to write a function to count the number of "on" bits in a character.  This is what I produced:

int CountBits(const char c)
{
    int count = 0;
    int x=0;
    for (; x<8; x++)
    {
        if (c & 1<<x)
            count++;
    }

    return count;
}

This led me into a more detailed problem in which I was asked to use that function to count the number of bits in an array of strings.  I initially produced this on the whiteboard:

int CountStringsBits(char** strArray, int numstrings)
{
    if (!strArray)
        return 0;

    int count = 0;
    for (int x=0; x<numstrings; x++)
    {
        for (int y=0; y < strlen(strArray[x]); y++)
        {
            count += CountBits(strArray[x][y]);
        }
    }
    return count;
}

While this does work, I realized that it can be done better and faster with a simple hash table to save the counts of previously counted characters.  I also moved the strlen function out of the inner loop.

int CountStringsBits(char** strArray, int numstrings)
{
    if (!strArray)
        return 0;

    int bitArray[128];  //simple hash table
    memset(bitArray, 0, sizeof(bitArray));
    int nstr, count = 0, x=0, y=0;
    char c;
    for (; x<numstrings; x++)
    {
        if (!strArray[x]) // make sure we have a string
            continue;
        nstr = strlen(strArray[x]);
       
        for (y=0; y < nstr; y++)
        {
            c =  strArray[x][y];
            if (bitArray[c] == 0)
                count += bitArray[c] = CountBits(c);
            else
                count += bitArray[c];
        }
    }
    return count;
}

Thanks for reading!