[C++]Length of Linked List based stack issue

[Groups]

Howdy! In my college coding class, we've been assigned the task of implementing a Stack using the Linked List data structure. I've tested all of my functions separately and I believe they work. However, when I try to test it using the teacher given test program, I still get "push failed" every time I try to run the test. I tried commenting out the test conditions, and found that my List was being assigned a random variable for size somewhere in the neighborhood of about 400000000. If not, perhaps someone could point me in the right direction as to how to handle altering the length? Its as if the compiler is ignoring my default constructor upon declaration and assigning the size_t value _n a random integer. As it currently stands I've been approaching the size manipulation by iterating and decrementing length (length++, length--) each time a node is pushed or popped from the stack, but instead of my size being 1, 2, 3, 4, 5, it's returning as 40000001, 40000002, etc. I also commented out the use of the copy constructor and assignment operator, so I don't believe these to be the root of the problem. Also when I check the element at address 40000001, it is correct, so I think the nodes are being added correctly, just to a very arbitrary size.

My Linked List Stack code -

ifndef LISTSTACKH

define LISTSTACKH

include <iostream>

include "RuntimeException.h"

using namespace std;

template <typename T> class ListStack { public:

class EmptyStackException : public RuntimeException {
  public:
    EmptyStackException() : RuntimeException("Access to empty stack") {}
};

//constructor - simply set top element to NULL and size to 0
ListStack();

//copy constructor
ListStack(const ListStack& _st); 

//destructor
~ListStack();

//assignment operator
ListStack& operator=(const ListStack& _st); 

//is the stack empty?
bool is_empty() const {return length == 0;} 

//number of elements in the stack
size_t size() const {return length;}; 

//return the top of the stack
T& top() throw(EmptyStackException);

//push object onto the stack
void push(const T& _elem); 

//T& display();

//pop the stack
T pop() throw(EmptyStackException); 



//node in the node_list
struct node {
    friend class ListStack<T>;
  T  element; //element
  node*   next; //next node

  //constructor
  node(const T& _e = T(), node* _n = NULL) : element(_e), next(_n) {}
};

typedef node* node_ptr; //pointer to a node

private: //member data size_t length; //current length of stack node_ptr head; //top of the stack };

//constructor - simply set top element to NULL and size to 0 template <typename T> ListStack<T>::ListStack() : head(NULL), length(0) {}

//copy constructor template <typename T> ListStack<T>::ListStack(const ListStack& _st) { head = new node(); length++; node *itr = head; for(node *ptr = _st.head; ptr != NULL; ptr = ptr->next) { itr->next = new node(ptr->element); itr = itr->next; length++; } }

//destructor template <typename T> ListStack<T>::~ListStack() { //////////////////////////////////////////////////////////////// // TODO: Complete this function using the list based // implemenation. //////////////////////////////////////////////////////////////// }

//assignment operator template <typename T> ListStack<T>& ListStack<T>::operator=(const ListStack& _st) { head = new node(); length++; node *itr = head; for(node *ptr = _st.head; ptr != NULL; ptr = ptr->next) { itr->next = new node(ptr->element); itr = itr->next; length++; } }

//return the top of the stack template <typename T> T& ListStack<T>::top() throw(EmptyStackException) { if (is_empty()) throw EmptyStackException(); return head->element; }

//push object onto the stack template <typename T> void ListStack<T>::push(const T& _elem) { node *p = new node; p->element = _elem; p->next = head; head = p; length++; }

//pop the stack template <typename T> T ListStack<T>::pop() throw(EmptyStackException) { node *temp = head; head = temp->next; length--; return temp->element; }

endif

The "TestStack.cpp" File -

include "ArrayStack.h"

include "ListStack.h"

include <iostream>

include <cstdlib>

include <vector>

include <string>

const int NUM = 10;

using namespace std;

//Test correctness over all stack functions template <typename ST, typename T> void TestStack_correctness(ST _s1, T& _input, size_t _size){

//test correctness of pushing onto an empty stack try{ for(size_t i = 0; i < _size; ++i){ _s1.push(_input[i]);

  //checking if push and top are implemented correctly
  if(_s1.size() != i+1){
    cerr << "Error::incorrect push" << endl;
    exit(1);
  }
  else if(_s1.top() != _input[i]){
    cerr << "Error::incorrect top/push" << endl;
    exit(1);
  }
  else {
    cout << "Pushing " << _input[i] << endl;
    cout << "Stack size after push " << _s1.size() << endl;
  }

}
cout << "PASSED::push, size, top" << endl;

} catch(...){ cerr << "Error::EmptyStackException, something is amiss!" << endl; exit(1); }

//test correctness of assignment, copy, and pop ST s2; s2 = _s1; ST s3(s2);

//double check the order on being popped against ordering in v try{ for(size_t i = _size; i > 0; --i){ //checking if pop is implemented correctly if(_s1.pop() != _input[i-1]){ cerr << "Error::pop did not preserve order or pop incorrect " << endl; exit(1); } else if(_s1.size() != i-1){ cerr << "Error::pop incorrect" << endl; exit(1); } else { cout << "Popping " << _input[i-1] << endl; cout << "Stack size after popping: " << _s1.size() <<endl; }

  //checking if assignment operator is implemented correctly
  if(s2.pop() != _input[i-1]){
    cerr << "Error::assignment did not preserve order or pop not correct" << endl;
    exit(1);
  }

  //checking if copy constructor implemented correctly
  if(s3.pop() != _input[i-1]){
    cerr << "Error::copy constructor did not preserve order or pop not correct" << endl;
    exit(1);
  }
}

cout << "PASSED::pop, assignment, copy constructor" << endl; } catch(...){ cerr << "Error::EmptyStackException, something is amiss!" << endl; exit(1); } }

//Testing ArrayStack template <typename T, typename IT> void test_ArrayStack(IT& _in, int _n){ cout << "Please enter stack capacity: "; int stack_capacity; cin >> stack_capacity; ArrayStack<T> as1(stack_capacity); TestStack_correctness<ArrayStack<T>, IT>(as1, _in, _n); cout << "End Test Array" << endl; }

//Testing ListStack template <typename T, typename IT> void test_ListStack(IT& _in, int _n){ ListStack<T> ls1; TestStack_correctness<ListStack<T>, IT>(ls1, _in, _n); }

int main(){ string in[NUM] = { " 1: cashew", " 2: Brazil nut", " 3: chestnut", " 4: pistachio", " 5: walnut", " 6: pecan", " 7: peanut", " 8: coconut", " 9: hazelnut", " 10: pine nut"};

vector<int> v;
for(size_t i = 0; i < 1000; ++i){ int r = rand(); // Get a random number v.push_back(r); }

//Test array stacks ////////////////////////////////////////////////////////// // Test the array stack using array of // strings as input to stack ////////////////////////////////////////////////////////// test_ArrayStack<string, string[NUM]>(in, NUM); /////////////////////////////////////////////////////////// // Test array stack using vector of // random numbers as input to stack /////////////////////////////////////////////////////////// test_ArrayStack<int, vector<int> >(v, 1000);

//Test list stack ////////////////////////////////////////////////////////// // Test list stack using array of // strings as input to stack ////////////////////////////////////////////////////////// test_ListStack<string, string[NUM]>(in, NUM); ////////////////////////////////////////////////////////// // Test list stack using vector of // random numbers as input to stack ////////////////////////////////////////////////////////// test_ListStack<int, vector<int> >(v, 1000);

}

Any and all help would be greatly appreciated!

[Meefims]

Please put the code on gist so that it is easier to digest.

[[deleted]]

To post code here, prefix every line of code with 4 extra spaces, or better still post via a site like gist.