Pathetic attempt of an array based stack

Question

Hi there,

This is my first pathetic attempt at C++. I did an array based stack in C++ and the destructor is throwing out some memory dump. I can't figure out what went wrong.

#include <stdio.h>
#include <iostream>
#include <exception>

using namespace std;

class FullStackException : public exception {
    virtual const char* what() const throw() {
        return "Stack is full.";
    }
} fsex;

class EmptyStackException : public exception {
    virtual const char* what() const throw() {
        return "Stack is empty.";
    }
} esex;

template <class D>
class ArrayBasedStack {
private:
    int t; //t represents top
    D *S;
    int arrSize;
public:
    ArrayBasedStack(int arraySize = 10);
    ~ArrayBasedStack();
    int size(); /*returns the number of elements stored*/
    void push(D&); /*inserts an element*/
    D pop(); /*removes and returns the last inserted element*/
    D top(); /*returns the last inserted element without removing it*/
    int isEmpty(); /*indicates whether no elements are stored*/
};

template <class D>
ArrayBasedStack<D>::ArrayBasedStack(int arraySize) {
    /* Elements are added from left to right */
    S = new D[arraySize];
    arrSize = arraySize;
    /* t keeps track of the index of the top element */
    t = -1;
}

template <class D>
ArrayBasedStack<D>::~ArrayBasedStack() {
    if(S != NULL) {
        int i = 0;
        for(i = 0; i < size(); i++) {
            S[i] = NULL;
        }
        cout << "about to delete S" << endl;
        delete[] S;
    }
}

template <class D>
int ArrayBasedStack<D>::size() {
    return t;
}

template <class D>
void ArrayBasedStack<D>::push(D& data) {
    if(t == arrSize) {
        throw fsex;
    } else {
        S[t] = data;
        t++;
    }
}

template <class D>
D ArrayBasedStack<D>::pop() {
    if(isEmpty()) {
        throw esex;
    }
    D element = S[t];
    S[t--] = NULL;
    return element;
}

/*
 * returns true if the stack is empty, false otherwise
 */
template <class D>
int ArrayBasedStack<D>::isEmpty() {
    return (t < 0);
}

int main(int argc, char *argv[]) {

    char inputs[][10] = {
        "str1"
    };

    char *i = NULL;

    ArrayBasedStack<char *> stack;
    i = inputs[0];
    stack.push(i);
    try {
        stack.pop();
    }
    catch(exception& ex) {
        cout << "ERR:" << ex.what() << endl;
    }
    return 0;
}

Regards, John Doe

Answer 1

The problem line is

    t = -1;

Should be

    t = 0;

because when you add first element, the following code is excecuted

    } else {
       S[t] = data;    // t == -1
       t++;
    }

Answer 2

The following is the culprit.

template <class D> 
void ArrayBasedStack<D>::push(D& data) { 
    if(t == arrSize) { 
        throw fsex; 
    } else { 
        S[t] = data;       // Should be S[++t] = data;
        t++;               // Comment out this line
    } 
} 

This implemntation assumes that 't' points to the topmost element on the stack rather than to the next available location for push

Note that operator [] and operator ++ have same precedence. Since they associate left-to-right, [] is evaluated before operator ++.

In your implementation, here is the problem. With t being initialized to -1, you are overwriting beyond the array subscript that is at S[-1] which leads to undefined behavior.

At least on my system the problem surfaces while trying to free the memory in destructor of the stack class. This is a classic example of a syptom being visible much after the goof-up has happened

Also would suggest push to take the parameters as D const &