bool isEmpty(): o Return true if there is no element in queue, false otherwise. int length(): o Returns count of number of elements in the queue. T dequeue(): o Returns and deletes element at front of queue. T front(): o Returns element at the front of queue without deleting it. void enqueue(T item): o Add item to the end of queue. ~Queue(): o Deallocate any memory your data structure is holding. Queue(const Queue& otherQueue): o Copy all elements of otherQueue into the new queue. QUEUE: Member functions: Write implementation for following methods as described here. bool isEmpty(): o Return true if there is no element in stack, false otherwise. int length(): o Returns count of number of elements in the stack. T pop(): o Return and delete top of the stack. T top(): o Returns top of stack without deleting it. void push(T item): o Pushes item at top of the stack. ~Stack: o Deallocate any memory your data structure is holding. Stack(const Stack& otherStack): o Copies all elements from otherStack to the new stack. Member functions: Write implementation for following methods as described here. You are allowed to access all members of LinkedList for your implementation of stack (and queue). STACK: Stack class contains LinkedList type object. As Part 1 is a pre-requisite for this part so you must have attempted Part 1 before you attempt this part. PART 2: STACKS AND QUEUES In this part, you will use your implementation of a linked list to write code for different methods of stacks and queues. int length(): o Returns number of nodes in the list. Void deleteTail(): o Delete tail of the list. void deleteHead(): o Delete head of the list. void deleteElement(T item): o Find the element item and delete it from the list. ListItem *searchFor (T item): o Returns pointer to item if it is in list, returns null otherwise. ListItem *getTail(): o Returns pointer to tail. ListItem *getHead(): o Returns pointer to the head of list. void InsertAfter(T toInsert, T afterWhat): o Traverse the list to find afterWhat and insert the toInsert after it. void InsertAtTail(T item): o Inserts item at the end of the linked list. ~LinkedList(): o Never forget to deallocate the memory! void InsertAtHead(T item): o Inserts item at start of the linked list. LinkedList(const LinkedList& otherList): o Simple copy constructor, given pointer to otherList this constructor copies all elements from otherList to new list. LinkedList(): o Simple default constructor. Member functions: Write implementation for the following methods as described here. NOTE: When implementing functions pay special attention to corner cases such as deleting from an empty list. However, you are only allowed to make changes in LinkedList.cpp file. You are also given a file, test1.cpp for checking your solution. The class LinkedList implements the linked list which contains pointers to head and tail and other function declarations. The template ListItem in LinkedList.h represents a node in a linked list. The basic layout of a linked list is given to you in the LinkedList.h file. Students are strongly advised that any act of plagiarism will be reported to the Disciplinary Committee PART 1: DOUBLY LINKED LIST In this assignment, you will be applying what you learnt in class to implement different functionalities of a linked list efficiently. All submissions are subject to automated plagiarism detection. Students must indicate any assistance they received. Students cannot copy code from the Internet. Students must be prepared to explain any program code they submit. Students must not share actual program code with other students. The course policy about plagiarism is as follows: 1. Start early as the assignment would take time. Here is how you can access the Mars server: Mars hostname: 203.135.62.10 Mars port number: 46002 Username: your-roll-number (e.g., 19100132) Password: your-roll-number You can log into Mars using ssh (ssh -p 46002 ) or telnet. The server is accessible from outside LUMS, therefore, you can log into Mars from home too. Your Linux accounts have been created on the Mars server. Please note that your code must compile at the mars server under the Linux environment. You may test your implemented data structures using the test cases provided to you. In this assignment, you are required to implement a linked list, stack, queue, and a simple version control system.
0 Comments
Leave a Reply. |