2017 Fall CIS200 Lab 8 Stack and Queue Release date: November 8, 2017 Due Date: November 15, 2017 Linked list is a perfect data structure for the implementation of stack and queue. Especially for the queue, it avoids the headaches of wrapping-around manipulation for a queue implemented by an array. In this project, you are requested to implement both stack and queue by using a linked list (not an array). NOTE: NOT ALL TEST CASES ARE COVERED IN THE CODE SEGMENTS BELOW. PART OF YOUR GRADE IS DETERMINED BY WHAT ADDITIONAL TEST CASES YOU IDENTIFY AND TEST. Highlight in the test plan AND the input and output files where the defect is occurring. Part 1 Develop and test individually Implement a template class Stack as defined by the following skeleton: template class Stack { private: NodeType* topPtr; // points to a singly-linked list public: Stack( ); // default constructor: Stack is created and empty Stack(const Stack &x); // copy constructor: implicitly called for a // deep copy void MakeEmpty(); // Stack is made empty; you should deallocate all the // the nodes of the linked list bool IsEmpty( ); // test if the stack is empty bool IsFull( ); // test if the stack is full; assume MAXITEM=5 int length( ); // return the number of elements in the stack void Print( ); // print the value of all elements in the stack in the // sequence from the top to bottom void Push(ItemType x); // insert x onto the stack void Pop(ItemType &x); // delete the top element from the stack // Precondition: the stack is not empty ~Stack(); // Destructor: memory for nodes deallocated }; 2 template struct NodeType { ItemType info; NodeType* next; }; In you main( ) routine, you need to test your class in the following cases: Stack IntStack; int x; IntStack.Pop(x); IntStack.Push(11); IntStack.Push(22); cout << "int length 1 = " << IntStack.length() << endl; IntStack.Pop(x); IntStack.Push(33); cout << "int length 2 = " << IntStack.length() << endl; cout << The int stack contains: << endl; IntStack.Print(); IntStack.Push(44); IntStack.Push(55); IntStack.Push(66); if(IntStack.IsFull() == false) cout << The int stack is not full ! << endl; else cout << The int stack is full ! << endl; Stack IntStack2(IntStack); cout << The int stack2 contains: << endl; IntStack2.Print(); IntStack2.MakeEmpty(); cout << The int stack2 contains: << endl; IntStack2.Print(); Stack FloatStack; float y; FloatStack.Pop(y); FloatStack.Push(7.1); cout << "float length 1 = " << FloatStack.length() << endl; FloatStack.Push(2.3); FloatStack.Push(3.1); cout << "float length 2 = " << FloatStack.length() << endl; FloatStack.Pop(y); cout << The float stack contains: << endl; FloatStack.Print(); Stack FloatStack2 = FloatStack; cout << The float stack 2 contains: << endl; FloatStack2.Print(); FloatStack.MakeEmpty(); cout << The float stack 3 contains: << endl; FloatStack2.Print(); 3 Part 2 Develop and test individually Implement a template class Queue as defined by the following skeleton: template class Queue { private: NodeType* front; // It points to the front of a singly-linked list NodeType* rear; // It points to the end of a singly-linked list public: Queue( ); // default constructor: Queue is created and empty Queue(const Queue &x); // copy constructor: implicitly called // for a deep copy void MakeEmpty(); // Queue is made empty; you should deallocate all // the nodes of the linked list bool IsEmpty( ); // test if the queue is empty bool IsFull( ); // test if the queue is full; assume MAXITEM=5 int length( ); // return the number of elements in the queue void Print( ); // print the value of all elements in the queue in the // sequence from the front to rear void Enqueue(ItemType x); // insert x to the rear of the queue // Precondition: the queue is not full void Dequeue(ItemType &x); // delete the element from the front of the queue // Precondition: the queue is not empty ~Queue(); // Destructor: memory for the dynamic array needs to be deallocated }; 4 In you main( ) routine, you need to test your class in the following cases: QueueIntQueue; int x; IntQueue.MakeEmpty(); IntQueue.Dequeue(x); IntQueue.Enqueue(10); IntQueue.Enqueue(20); IntQueue.Enqueue(30); IntQueue.Enqueue(40); cout << "int length 3 = " << IntQueue.length() << endl; IntQueue.Dequeue(x); cout << "int length 4 = " << IntQueue.length() << endl; cout << The int queue contains: << endl; IntQueue.Print(); if(IntQueue.IsFull() == false) cout << The int queue is not full ! << endl; else cout << The int queue is full ! << endl; QueueFloatQueue; float y; FloatQueue.MakeEmpty(); FloatQueue.Dequeue(y); FloatQueue.Enqueue(7.1); cout << "float length 3 = " << FloatQueue.length() << endl; FloatQueue.Dequeue(y); cout << "float length 3 = " << FloatQueue.length() << endl; FloatQueue.Enqueue(2.3); FloatQueue.Enqueue(2.3); cout << "float length 4 = " << FloatQueue.length() << endl; FloatQueue.Enqueue(3.1); FloatQueue.Dequeue(y); cout << The float queue contains: << endl; FloatQueue.Print(); Queue FloatQueue2 = FloatQueue; cout << The float queue 2 contains: << endl; FloatQueue2.Print(); FloatQueue.MakeEmpty(); cout << The float queue 3 contains: << endl; FloatQueue2.Print(); Part 3 Combine Part 1 and Part 2 into a single program. Implement the stack and queue to implement a priority queue for a set of integers, doubles, and characters. The queue is first-in-first-out based on ascending order. Use the stack to reorder the queue to insert the item in the correct sequence (i.e. unload the end of the queue into the stack until the correct location is found to enqueue the item, empty the stack to refill the queue entries) 5 Assumptions: Input file name to be entered by the user. No edits of data, only correct values and formats included in the input file. First line of file will have a character representing type of data in the file I(nteger), R(eal), C(haracter) Followed by actions on separate line: A(dd) value D(equeue) L(ength) P(rint) Example: I D P L A 1 A 5 A 1 A 1 A 2 A 4 L P D A 4 .... Echo print action and any message (e.g. attempted to add to full queue) to screen and output file named lab8.txt Turn-in must include C++ code files and screen prints for all 3 parts and all test input and output files be sure to label to indicate which output files is associated with integer, real and character data.