You may want to take a look at the Iterators' page, and the page for lists with iterators.
In this project, we will design two templated classes called Stack and Queue. These two classes are based on linked lists. All classes and functions in this course will be templated unless otherwise instructed by me.
1. Linked List Functions (list.h)
DO NOT implement a linked list class. We are simply writing low level functions that will perform linked list operations. We will use these functions to implement our Stack and Queue:
First, define a node struct:
template <class T> struct node{ T _item; node<T>* _next;
node<T>* _prev;
node(const T& item = T(), node<T>* next = NULL, node<T>* prev = NULL):
_item(item),
_next(next),
_prev(prev){} friend ostream& operator << (ostream& outs, const node<T>& print_me){ outs<<"["<<print_me._item<<"]->"; return outs; } };
Now, define the following functions with this exact signature and functionality:
//Linked List General Functions: template <typename T> void _print_list(node<T>* head); //recursive fun! :) template <typename T> void _print_list_backwards(node<T> *head); //return ptr to key or NULL template <typename T> node<T>* _search_list(node<T>* head, T key); template <typename T> node<T>* _insert_head(node<T> *&head, T insert_this); //insert after ptr: insert head if marker null template <typename T> node<T>* _insert_after(node<T>*& head, node<T> *after_this, T insert_this); //insert before ptr: insert head if marker null template <typename T> node<T>* _insert_before(node<T>*& head, node<T>* before_this, T insert_this); //ptr to previous node template <typename T> node<T>* _previous_node(node<T>* prev_to_this); //delete, return item template <typename T> T _delete_node(node<T>*& head, node<T>* delete_this); //duplicate the list... template <typename T> node<T>* _copy_list(node<T>* head);
//duplicate the list, return pointer to last node in dest...
// use this function in your queue big three
template <typename T> node<T> *_copy_list(node<T> *&dest, node<T> *src);
//delete all the nodes template <typename T> void _clear_list(node<T>*& head); //_item at this position template <typename T> T& _at(node<T>* head, int pos);
2. Define a Queue class (use upper case Q for the name) as follows: (queue.h)
template <typename T> class Queue { public: class Iterator{ public: friend class Queue; //give access to list to access _ptr Iterator(){_ptr = NULL;} //default ctor Iterator(node<T>* p){} //Point Iterator to where // p is pointing to T operator *(){} //dereference operator bool is_null(){} //true if _ptr is NULL friend bool operator !=(const Iterator& left, const Iterator& right) //true if left != right {} friend bool operator ==(const Iterator& left, const Iterator& right) //true if left == right {} Iterator& operator++(){ //member operator:++it // or ++it = new_value } friend Iterator operator++(Iterator& it, int unused){ //friend operator: it++ } private: node<T>* _ptr; //pointer being encapsulated }; Queue(); Queue(const Queue<T>& copyMe); ~Queue(); Queue& operator=(const Queue<T>& RHS); bool empty(); T front(); T back(); void push(T item); T pop(); Iterator begin() const; //Iterator to the head node Iterator end() const; //Iterator to NULL void print_pointers(); int size() const { return _size; } template<typename TT> friend ostream& operator << (ostream& outs, const Queue<TT>& printMe); private: node<T>* _front; node<T>* _rear; int _size; };
3. Define a Stack class (upper case S for the name) as follows: (stack.h)
template <typename ITEM_TYPE> class Stack{ public: class Iterator{ public: friend class Stack; //give access to list to access _ptr Iterator(){_ptr = NULL;} //default ctor Iterator(node<ITEM_TYPE>* p){} //Point Iterator to where // p is pointing to ITEM_TYPE operator *(){} //dereference operator bool is_null(){return _ptr == NULL;} //true if _ptr is NULL friend bool operator !=(const Iterator& left, const Iterator& right) //true if left != right {return left._ptr != right._ptr;} friend bool operator ==(const Iterator& left, const Iterator& right) //true if left == right {} Iterator& operator++(){ //member operator:++it // or ++it = new_value } friend Iterator operator++(Iterator& it, int unused){ //friend operator: it++ assert(it._ptr!=NULL); } private: node<ITEM_TYPE>* _ptr; //pointer being encapsulated }; Stack(); Stack(const Stack<ITEM_TYPE>& copyMe); ~Stack(); Stack<ITEM_TYPE>& operator=(const Stack<ITEM_TYPE>& RHS); ITEM_TYPE top(); bool empty(); void push(ITEM_TYPE item); ITEM_TYPE pop(); template<typename T> friend ostream& operator<<(ostream& outs, const Stack<T>& printMe); Iterator begin() const; //Iterator to the head node Iterator end() const; //Iterator to NULL int size() const { return _size; } private: node<ITEM_TYPE>* _top; int _size; };
4. Test your Stack and Queue classes by writing a pair of functions to output what is shown below:
1. declare an instance of the Stack (Queue) class, in a for loop, push 0..9 into the object, print the object
2. Declare another object using the copy constructor to be a copy of this first object.
3. while the container is not empty, pop (show the popped item in braces { } )and reprint the object
4. when the object is empty, assign the second object back into the first and reprint both objects.
This should test all the functions of the class as well as the big three functions.
Output For Stack:
s: [9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->||| s2: [9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->||| { 9 } [8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->||| { 8 } [7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->||| { 7 } [6]->[5]->[4]->[3]->[2]->[1]->[0]->||| { 6 } [5]->[4]->[3]->[2]->[1]->[0]->||| { 5 } [4]->[3]->[2]->[1]->[0]->||| { 4 } [3]->[2]->[1]->[0]->||| { 3 } [2]->[1]->[0]->||| { 2 } [1]->[0]->||| { 1 } [0]->||| { 0 } ||| assigning s back to s2: s: [9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->||| s2: [9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]->|||
Output For Queue:
q: [0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->||| q2: [0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->||| { 0 } [1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->||| { 1 } [2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->||| { 2 } [3]->[4]->[5]->[6]->[7]->[8]->[9]->||| { 3 } [4]->[5]->[6]->[7]->[8]->[9]->||| { 4 } [5]->[6]->[7]->[8]->[9]->||| { 5 } [6]->[7]->[8]->[9]->||| { 6 } [7]->[8]->[9]->||| { 7 } [8]->[9]->||| { 8 } [9]->||| { 9 } ||| assigning q back to q2: q: [0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->||| q2: [0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->|||