Background:
The singly linked list implementation that is provided implements the stack abstract data type (ADT). Nodes are pushed onto the head of the list and popped off the head of the list.
The queue ADT (DSAA 4.3) implements functionality that is like standing in line waiting to buy tickets at a movie theater. The ‘front’ of the line is where you stand when you are the next person called by the cashier to buy a ticket. The ‘back’ of the line is where you enter to wait your turn. In other countries, people actually say they are “waiting in the queue”, though in America it’s usually called “standing in line”. To use our singly linked list to implement the queue ADT, we would need to add a ‘tail’ variable pointing to the last node in the list. Then we would push nodes onto the head of the list and pop nodes off the tail of the list. It would look like this:
You can refer to the book’s Linked Queue (DSAA 4.3.2) for an implementation example. In some implementations for convenience, pop() also returns the value of the removed element. Equivalent names for push and pop are enqueue and dequeue (these are used in the book). We will stick with push and pop because dequeue is too similar to deque, discussed next.
The deque ADT (pronounced “deck”) is an enhanced version of the queue ADT. Rather than just popping off the tail and pushing at the head, the deque ADT allows popping and pushing at both ends of the linked list. In essence, the deque provides the same functionality as two stacks (DSAA 4.2). In this assignment, you will implement the deque ADT in a templated class called LinkedDeq by inheriting from the class SLinkedList (provided). Your implementation will have one important limitation – you will not be allowed to add a tail pointer to the last node.
Objectives:
- Apply OOP principles to software design decisions
- Use class inheritance for templated C++ classes
- Implement a sort routine
Requirements:
1) Follow all of the 232 Coding Standards. I will be less lenient on violations than I have been in prior assignments.
2) Using the supplied code, implement a deque by extending SLinkedList. Name the child class
LinkedDeq and implement the following methods:
back(): Return the deque’s last element.
push_back(e): Insert e at the end of the deque.
pop_back(): Return the last element of the deque and delete the last node.
sort(): Sort the list (more info below)
3) Reminder: Do not add a tail pointer to the last node. Any time you need access to the last node, you must traverse the list to get to it.
4) Overload the subscript operator to give your list the ability to be accessed with array-like syntax.
5) Use the createList() method to fill the deque with 10 random numbers.
6) Insertion sort is a common sorting algorithm. On linked lists, it works by starting with a new, empty list. Each node from the head of the old list is moved to the new list and put into its correct, sorted position. The loop ends when the old list is empty. Implement an insertion sort method.
7) In main(), write a for loop and use the subscript operator to print the list after it has been sorted.
8) Add a Node pointer field called bottom to the LinkedDeq class. This field will be used as a ‘divider’ to separate the list into two parts so that it can be used as two stacks. This field should not be used in traversals as a ‘shortcut’ to the last node in the list.
9) Use createList() to create a new deque filled with 20 random numbers. Assign bottom to a random position somewhere in the middle 1/3 of the list. Now using your deque as two stacks, modify the sort method with additional parameters and logic to sort each stack in ascending order. A stack sorted in ascending order has the smallest number at the bottom and the largest number at the top. For example, if a deque looked like this (the ‘b’ indicates that bottom is pointing at the node with 12 in its elem field):
{4, 3, 8, 1, 7, b, 12, 14, 6, 2}
then the deque with its two sorted stacks would look like this:
{8, 7, 4, 3, 1, b, 2, 6, 12, 14}
10) Your output should include the original list, the sorted deque, and the deque as two sorted stacks with appropriate descriptive text. When printing the two sorted stacks, print a ‘b’ before the elem field of the node it is pointing to.
11) You may use only language features discussed in class or presented in the book up to the date the assignment is due. Your submission must be your own work. You may not utilize any code outside of that provided in class or in the book and you may not post any provided code on publicly accessible websites. Submit only what is requested.
Attachment:- assignment.docx