template class ListStack { private: class SNode { public: SNode (T data, SNode *next) { this -> data = data; this -> next = next; } T data; SNode *next; }; SNode *head; // head pointer for the linked list bool elastic; // true if stack is elastic (has infinite capacity) int capacity; // stack capacity (only meaningful if "elastic" is false int count; // number of values on stack public: // creates an "elastic" stack ListStack (); // creates a stack with a fixed capacity ListStack (int capacity); ListStack (const ListStack &otherStack); ~ListStack (); // throws an "overflow_error" exception if the stack has a fixed // capacity and is full. void push (T value); // throws an "overflow_error" exception if the stack is empty T pop (); bool isEmpty() const { return count == 0; } int getcount() const { return count; } // copies contents only (capacity attributes are not copied). // throws an "overflow_error" exception if the destination stack // has a fixed capacity and this is not large enough. ListStack& operator= (const ListStack &otherStack); }; template ListStack::ListStack () { head = NULL; elastic = true; count = 0; } template ListStack::ListStack (int capacity) { if (capacity <= 0) { throw invalid_argument ("ListStack::ListStack - invalid capacity"); } head = NULL; elastic = false; this -> capacity = capacity; count = 0; } template ListStack::ListStack (const ListStack &otherStack) { // we must create a copy of the linked list in the other stack SNode *c, *l, *n; // so far the list we're creating does not have a last node l = head = NULL; // for all node in the other stack's list for (c = otherStack.head; c != NULL; c = c -> next) { // create a copy of the node n = new SNode(c -> data, NULL); // make the last node in the list being created point to it if (l == NULL) { // no last node yet head = n; // new node goes at the start of the list } else { l -> next = n; } // our new node is now the last node l = n; } count = otherStack.count; elastic = otherStack.elastic; capacity = otherStack.capacity; } template ListStack::~ListStack () { // we must roll up the entire linked list SNode *c; while (head != NULL) { c = head; head = head -> next; delete c; } } template void ListStack::push (T value) { if (!elastic && (count == capacity)) { throw overflow_error ("ListStack::push - stack overflow"); } head = new SNode(value, head); count++; } template T ListStack::pop () { SNode *c; T result; if (head == NULL) { throw overflow_error ("ListStack::pop - stack underflow"); } c = head; head = head -> next; count--; result = c -> data; delete c; return result; } // *** NOT IMPLEMENTED *** (left as an exercise!) // ListStack& ListStack::operator= (const ListStack &otherStack) {}