/* stack_312_LL.h CS 312 Fall 2018 a very simple linked list Stack ADT */ #ifndef STACK_312_H #define STACK_312_H #include // Provides size_t #include using namespace std; template class Stack_312 { public: // typedef int value_type; typedef int size_type; Stack_312(); //Copy constructor Stack_312(const Stack_312 & src); /**************************** makeEmpty Function: Removes all the items from the stack. Preconditions: Stack has been initialized Postconditions: All the items have been removed *****************************/ void makeEmpty(); /**************************** isEmpty Function: Checks to see if there are any items on the stack. Preconditions: Stack has been initialized Postconditions: Returns true if there are no items on the stack, else false. *****************************/ bool isEmpty() const; /**************************** isFull Function: Determines if you have any more room to add items to the stack Preconditions: Stack has been initialized Postconditions: Returns true if there is no more room to add items, else false *****************************/ bool isFull() const; /**************************** push Function: Adds newItem to the top of the stack. Preconditions: Stack has been initialized and is not full. Postconditions: newItem is at the top of the stack. *****************************/ void push(const ItemType &); /**************************** pop Function: Removes topItem from stack and returns it. Preconditions: Stack has been initialized and is not empty. Postconditions: Top element has been removed from stack and item is a copy of the removed element. *****************************/ ItemType pop(); private: struct Node { ItemType value; Node *next; }; Node *head; }; /******************************* / Function implementations ********************************/ template Stack_312::Stack_312 () { head = NULL; } template Stack_312::Stack_312(const Stack_312 & src) { if (src.head == NULL) { head = NULL; } else { Node *temp; Node *prev = NULL; for (Node *p = src.head; p != NULL; p=p->next) { temp = new Node; temp->value = p->value; temp->next = NULL; if (prev == NULL) prev = temp; else { prev->next = temp; prev = temp; } if (p == src.head) head = temp; } } } template void Stack_312 ::makeEmpty() { Node *p = head; while (head != NULL) { head = head->next; delete p; p = head; } } template bool Stack_312 ::isEmpty() const { return head == NULL; } template bool Stack_312 ::isFull() const { return false; //temporary (could use the try/catch memory allocation) } template void Stack_312 ::push(const ItemType& newItem) { assert(!isFull()); Node *p = new Node; p->value = newItem; p->next = head; head = p; } template ItemType Stack_312 ::pop() { assert(!isEmpty()); ItemType temp = head->value; Node *p = head; head = head->next; delete p; return temp; } #endif