please answer these questions includes the three classes

1 [30 marks] (The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node SortedLinkedList.h / SortedLinkedList.h /A collection of data are stored in the 1ist by ascending order #1 fnde f define SORTEDLI ST SORTEDLIST using namespace std; H H template class SortedL,ist private: / The basic single 1inked list node type Nested nside of SortedList. struct NodeTy T data; NodeType* next; NodeType prev: NodeType (const T & d) datad; next - nullptr; prev = nullptr; public: class const iterator public: Public constructor for const iterator const iterator) current = nullptr; const T&operator* return retrieve ; const_iterator & operator++ ) current -Current-next return this: const_iterator & operator) cu rren t = current->prev; return this bool ope rator- const constitera tor & rhs ) const - re turn current rhs. current; bool operator!= { const const_iterator & rns } const re turn ! *this- protected: NodeType current; T & retricveconst return current->data; const_iterator NodeType p ) current = p; friend class SortedListcurrent -this-current->next; return *this, iterator & operator-- this->current return *this; this->current->prev; = protected: iterator NodeType p : const_iteratori p) friend class SortedListnext ); const_iterator beginc const return const_iterator( head->next ; Return iterator representing endmarker of list Mutator version is first, then accessor version. i terator end) return iterator tail const iterator endconst return const iterator( tail // Return number of elements currently in the list int size const return theSize; / Return true if the list is empty, false otherwise bool empty const return size0 void clear) while empty iterator temp(erase (tail->prev); If x is found, return x position; // If x is not fou nd, return the positio that Xshould be located iterator find const x) NodeType* ptr head->next; add your code Insert x before itr iterator insert iterator itr, const T &X NodeTypex newptrnew NodeType (x); NodeType* p = itr. current ; newptr-prevp-prev: newptr->next = p; p->prev-next - newptri p->prev = newptr; ++thesize; return iterator newptr; Erase item at itr terator erasef iterator itr) NodeType pitr.current: iterator retVal p->next p->prev->next = p->next; p-next-preprev: delete p; --thesize; return retVal; // add x in the sorted list, find the position that x should be inserted, and ther insert x iterator add item(cost T& add your code // remove x from the sorted list. // If x is in the sorted list, find the position of x, and then / If x is not in the sorted list, return the position thatx iterator remove item (const T &x remove x. should be located private: int theSize; NodeType* head; NodeType* tail; void init) head = new NodeType(0); tail-new NodeType (0); head->next- tail; tail->prev- head; #endif 1) Read the code carefully, and understand the nested classes const_iterator and iterator 2) Implement the member functions find, add item, and remove item based on the corresponding comments. The three functions all return an iterator clas:s 3) Write an application program that . creates an int type sorted list using SortedLinkedList class template . prompt the user to enter int values, and add these values to the sorted list, stop adding the values when the user enter 0 . print the sorted list using iterator * prompt the user to enter int values to be removed, remove the values from the sorted list, stop removing the values when the user enter 0 * print the sorted list using iterator. Three files should be submitted for this program question 1) the file SortedLinkedList.h which contains the implementation of SortedLinkedList class template, 2) the application file a2ql.cpp containing main) function, 3) a script file a2qlresult containing result. definition and Here are the sample runs Enter values in the sorted list: 3 6 2 951874 0 The sorted list is: 1 2 3 45 6 7 8 9 The values to be removed: 4 6 2 8 The sorted list 1 3 57 9 is: 2.[30 marks] (Stack Application Infix to Postfix Conversion) Write a program that uses the Stack class template to convert an infix arithmetic expression into a postfix arithmctic expression In infix form, the operator of an arithmetic statement is in-between every pair of operands For example a * (b c) (a + b)c In postfix form, the operands of an arithmetic statement appear followed by the operator One of the virtucs of postfix form is that expressions can be written without the need for parentheses. Here are some examples of arithmetic expressions written in postfix form a b// Equivalent to a b a bc+*/ Equivalent to a ( c) a b+c *// Equivalent to (a+ b) C Please write a C++ program that uses an operator stack to convert an infix arithmetic expression that the user enters into a postfix arithmetic expression. Users input the infix arithmetic expressions which only contains the operands, operators and parenthesis symbols. The character # marks the end of the expression. The operands are represented by single lowercase letters, i.e., a, b, c, d, etc, and the operators are +,-, * and / Assuming the expressions the users enter are all validated You may call the following functions in main function // checks if c is an operand bool is_operand (char c) return true; else return false // checks if c is an operator +, -, *, or / bool is_operator (char c) return true else return false // return the precedence of an operator int get_operator_precedence (char op) int prec0; prec 1; prec =2; prec-; else if (op--'*Il op--') else return prec; Three files should be submitted for this program question 1) the file stack. h which contains the definition and implementation of Stack class template, 2) the application file a2q2.cpp containing main ) function, 3) a script file a2q2result containing result. Here are the sample runs: The infix expression: a+b- (c+d) *e The postfix expression: ab+cd+e- The infix expression: a" (b+c)-e The postfix expression: abc+ e- 3. [40 marks] (Deque) A deque is a data structure consisting of a list of items on which the following operations are possible: a. push (x) : Insert item x on the front end of the deque b. pop ( Remove the front item from the deque and return it. c. inject (x) Insert item x on the rear end of the deque d. eject : Remove the rear item from the deque and return it Write routines to support the deque that take O(1) time per operation (the operations that take O(n) will be given 0 point). Write an application file a2q3.cpp containing main) function to test if Deque class works correctly Three files should be submitted for this program question 1) the file Deque.h which contains the definition and implementation of Deque class template, 2) the application file a2q3.cpp containing main() function, 3) a script file a2q3result containing result. Here are the sample runs: Push values in deque: 1 2 3 4 5 Inject values in deque 1 2 3 4 5 The front element popped out is 5 The rear element ejected out is5 The front element popped out is 4 The rear element ejected out is 4 1 [30 marks] (The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node SortedLinkedList.h / SortedLinkedList.h /A collection of data are stored in the 1ist by ascending order #1 fnde f define SORTEDLI ST SORTEDLIST using namespace std; H H template class SortedL,ist private: / The basic single 1inked list node type Nested nside of SortedList. struct NodeTy T data; NodeType* next; NodeType prev: NodeType (const T & d) datad; next - nullptr; prev = nullptr; public: class const iterator public: Public constructor for const iterator const iterator) current = nullptr; const T&operator* return retrieve ; const_iterator & operator++ ) current -Current-next return this: const_iterator & operator) cu rren t = current->prev; return this bool ope rator- const constitera tor & rhs ) const - re turn current rhs. current; bool operator!= { const const_iterator & rns } const re turn ! *this- protected: NodeType current; T & retricveconst return current->data; const_iterator NodeType p ) current = p; friend class SortedListcurrent -this-current->next; return *this, iterator & operator-- this->current return *this; this->current->prev; = protected: iterator NodeType p : const_iteratori p) friend class SortedListnext ); const_iterator beginc const return const_iterator( head->next ; Return iterator representing endmarker of list Mutator version is first, then accessor version. i terator end) return iterator tail const iterator endconst return const iterator( tail // Return number of elements currently in the list int size const return theSize; / Return true if the list is empty, false otherwise bool empty const return size0 void clear) while empty iterator temp(erase (tail->prev); If x is found, return x position; // If x is not fou nd, return the positio that Xshould be located iterator find const x) NodeType* ptr head->next; add your code Insert x before itr iterator insert iterator itr, const T &X NodeTypex newptrnew NodeType (x); NodeType* p = itr. current ; newptr-prevp-prev: newptr->next = p; p->prev-next - newptri p->prev = newptr; ++thesize; return iterator newptr; Erase item at itr terator erasef iterator itr) NodeType pitr.current: iterator retVal p->next p->prev->next = p->next; p-next-preprev: delete p; --thesize; return retVal; // add x in the sorted list, find the position that x should be inserted, and ther insert x iterator add item(cost T& add your code // remove x from the sorted list. // If x is in the sorted list, find the position of x, and then / If x is not in the sorted list, return the position thatx iterator remove item (const T &x remove x. should be located private: int theSize; NodeType* head; NodeType* tail; void init) head = new NodeType(0); tail-new NodeType (0); head->next- tail; tail->prev- head; #endif 1) Read the code carefully, and understand the nested classes const_iterator and iterator 2) Implement the member functions find, add item, and remove item based on the corresponding comments. The three functions all return an iterator clas:s 3) Write an application program that . creates an int type sorted list using SortedLinkedList class template . prompt the user to enter int values, and add these values to the sorted list, stop adding the values when the user enter 0 . print the sorted list using iterator * prompt the user to enter int values to be removed, remove the values from the sorted list, stop removing the values when the user enter 0 * print the sorted list using iterator. Three files should be submitted for this program question 1) the file SortedLinkedList.h which contains the implementation of SortedLinkedList class template, 2) the application file a2ql.cpp containing main) function, 3) a script file a2qlresult containing result. definition and Here are the sample runs Enter values in the sorted list: 3 6 2 951874 0 The sorted list is: 1 2 3 45 6 7 8 9 The values to be removed: 4 6 2 8 The sorted list 1 3 57 9 is: 2.[30 marks] (Stack Application Infix to Postfix Conversion) Write a program that uses the Stack class template to convert an infix arithmetic expression into a postfix arithmctic expression In infix form, the operator of an arithmetic statement is in-between every pair of operands For example a * (b c) (a + b)c In postfix form, the operands of an arithmetic statement appear followed by the operator One of the virtucs of postfix form is that expressions can be written without the need for parentheses. Here are some examples of arithmetic expressions written in postfix form a b// Equivalent to a b a bc+*/ Equivalent to a ( c) a b+c *// Equivalent to (a+ b) C Please write a C++ program that uses an operator stack to convert an infix arithmetic expression that the user enters into a postfix arithmetic expression. Users input the infix arithmetic expressions which only contains the operands, operators and parenthesis symbols. The character # marks the end of the expression. The operands are represented by single lowercase letters, i.e., a, b, c, d, etc, and the operators are +,-, * and / Assuming the expressions the users enter are all validated You may call the following functions in main function // checks if c is an operand bool is_operand (char c) return true; else return false // checks if c is an operator +, -, *, or / bool is_operator (char c) return true else return false // return the precedence of an operator int get_operator_precedence (char op) int prec0; prec 1; prec =2; prec-; else if (op--'*Il op--') else return prec; Three files should be submitted for this program question 1) the file stack. h which contains the definition and implementation of Stack class template, 2) the application file a2q2.cpp containing main ) function, 3) a script file a2q2result containing result. Here are the sample runs: The infix expression: a+b- (c+d) *e The postfix expression: ab+cd+e- The infix expression: a" (b+c)-e The postfix expression: abc+ e- 3. [40 marks] (Deque) A deque is a data structure consisting of a list of items on which the following operations are possible: a. push (x) : Insert item x on the front end of the deque b. pop ( Remove the front item from the deque and return it. c. inject (x) Insert item x on the rear end of the deque d. eject : Remove the rear item from the deque and return it Write routines to support the deque that take O(1) time per operation (the operations that take O(n) will be given 0 point). Write an application file a2q3.cpp containing main) function to test if Deque class works correctly Three files should be submitted for this program question 1) the file Deque.h which contains the definition and implementation of Deque class template, 2) the application file a2q3.cpp containing main() function, 3) a script file a2q3result containing result. Here are the sample runs: Push values in deque: 1 2 3 4 5 Inject values in deque 1 2 3 4 5 The front element popped out is 5 The rear element ejected out is5 The front element popped out is 4 The rear element ejected out is 4