Stack Type File

// The class definition for StackType using templates class FullStack // Exception class thrown by Push when stack is full. {}; class EmptyStack // Exception class thrown by Pop and Top when stack is emtpy. {}; template class StackType { public: StackType(); // Class constructor. StackType(int max); // Parameterized constructor. ~StackType(); // Destructor bool IsFull() const; // Function: Determines whether the stack is full. // Pre: Stack has been initialized. // Post: Function value = (stack is full) bool IsEmpty() const; // Function: Determines whether the stack is empty. // Pre: Stack has been initialized. // Post: Function value = (stack is empty) void Push(ItemType item); // Function: Adds newItem to the top of the stack. // Pre: Stack has been initialized. // Post: If (stack is full), FullStack exception is thrown; // otherwise, newItem is at the top of the stack. ItemType Pop(); // Function: Removes top item from the stack and returns it. // Pre: Stack has been initialized. // Post: If (stack is empty), EmptyStack exception is thrown; // otherwise, top element has been removed from stack. ItemType Peek(); // Function: Returns a copy of top item on the stack. // Pre: Stack has been initialized. // Post: If (stack is empty), EmptyStack exception is thrown; // otherwise, top element has been removed from stack. private: int top; int maxStack; ItemType* items; }; // The function definitions for class StackType. template StackType::StackType(int max) { maxStack = max; top = -1; items = new ItemType[maxStack]; } template StackType::StackType() { maxStack = 500; top = -1; items = new ItemType[maxStack]; } template bool StackType::IsEmpty() const { return (top == -1); } template bool StackType::IsFull() const { return (top == maxStack-1); } template void StackType::Push(ItemType newItem) { if (IsFull()) throw FullStack(); top++; items[top] = newItem; } template ItemType StackType::Pop() { if( IsEmpty() ) throw EmptyStack(); ItemType curret = items[top]; top--; return curret; } template ItemType StackType::Peek() { if (IsEmpty()) throw EmptyStack(); return items[top]; } template StackType::~StackType() { delete [] items; } Queue Type File

class FullQueue {}; class EmptyQueue {}; template class QueType { public: QueType(); // Class constructor. // Because there is a default constructor, the precondition // that the queue has been initialized is omitted. QueType(int max); // Parameterized class constructor. ~QueType(); // Class destructor. void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Post: If (queue is full) FullQueue exception is thrown // else newItem is at rear of queue. void Dequeue(ItemType& item); // Function: Removes front item from the queue and returns it in item. // Post: If (queue is empty) EmptyQueue exception is thrown // and item is undefined // else front element has been removed from queue and // item is a copy of removed element. private: int front; int rear; ItemType* items; int maxQue; }; template QueType::QueType(int max) // Parameterized class constructor // Post: maxQue, front, and rear have been initialized. // The array to hold the queue elements has been dynamically // allocated. { maxQue = max + 1; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } template QueType::QueType() // Default class constructor // Post: maxQue, front, and rear have been initialized. // The array to hold the queue elements has been dynamically // allocated. { maxQue = 501; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } template QueType::~QueType() // Class destructor { delete [] items; } template void QueType::MakeEmpty() // Post: front and rear have been reset to the empty state. { front = maxQue - 1; rear = maxQue - 1; } template bool QueType::IsEmpty() const // Returns true if the queue is empty; false otherwise. { return (rear == front); } template bool QueType::IsFull() const // Returns true if the queue is full; false otherwise. { return ((rear + 1) % maxQue == front); } template void QueType::Enqueue(ItemType newItem) // Post: If (queue is not full) newItem is at the rear of the queue; // otherwise a FullQueue exception is thrown. { if (IsFull()) throw FullQueue(); else { rear = (rear +1) % maxQue; items[rear] = newItem; } } template void QueType::Dequeue(ItemType& item) // Post: If (queue is not empty) the front of the queue has been // removed and a copy returned in item; // othersiwe a EmptyQueue exception has been thrown. { if (IsEmpty()) throw EmptyQueue(); else { front = (front + 1) % maxQue; item = items[front]; } } 

3. This programming problem deals with the template-based stack StackType and queue QueType implementations, and strings. (40 pts) You must use the provided StackType.h and QueType.h found in the provided TemplateStackDriver.zip and TemplateQueueDriver.zip files. Also, be certain to adhere to the example below in using the standard library std: :string as input arguments not a character array (char[] or char*) as input, since we will test it using strings. You are to create a function decode in a file stringdecoding.cpp as: std::string decode(std:string exp, std:zstring code) \{\} The function should iterate through each character in exp (see std:string at function) and take one of two actions: i. Characters in exp that are not also in the string code should be present in the output in normal, sequential order as they are encountered, without modification. ii. All characters in exp that are also present in the string code should be present in the output after the characters printed in part i AND entirely in reverse order. Sample input and output for reference is as follows: decode("czitqommta_ehmumt_nio_szozir_eulopupoa_yeht_","_acefhilnpst") // should return the following string: "zqommumozozruouoy_the_apple_is_in_the_attic" As alluded to above, the recommended approach is to: 1. Create StackTypes and QueTypess instances of the appropriate types and add characters to them until the end of string exp is reached. 2. Put together the output string using appropriate operations. Note You are free to use helper functions as desired; however, all your code must be included in the stringdecoding.cpp file. You must not modify the stackType or QueType files, rather you need to include the StackType and QueueType into the stringcoding.cpp file. Initializing Variables Remember to initialize your variables! You can not assume that int i; will set i equal to 0 . Instead, always set your variables to a value manually. Like so