Goals

This assignment is an individual assignment and you will work on it on your own. The goal of this assignment is to be able to use stacks and queues, and to master and have an in-depth understanding of such primitive ADTs. In this assignment you will build a more complex ADT using the primitive stack and queue ADTs. Moreover, an important goal of this assignment is to be able to analyze an ADT that you will build yourself using more primitive ADTs, and to be able to compute the time and space complexity using the Big-O notation. Based on that you are asked also to enhance your first implementation to achieve better performance.

Details

In this assignment you are required to build a Queue ADT using a Stack ADT. You are required to use the linked list stack implementation we presented in class and included in the lecture slides. You are required to use exactly two stack instances in your Queue ADT implementation.

In this assignment you are required to perform two attempts. In the first attempt, you are required to use the linked list stack implementation as is, and you are not allowed to change it, which will not result in a very optimum implementation; basically you are not allowed to use except the push and pop methods. Nevertheless, your implementation of the new Queue ADT should be as optimum and efficient as possible within these boundaries; using the linked list stack implementation as is.

In the second attempt, you will be allowed to introduce changes to the stack implementation to provide better performance and hence better running time. It is mandatory to utilize all object oriented techniques, such as inheritance, to minimized the amount of amendments as much as possible, and to provide copy and move constructors if needed to reduce memory operations overhead.

The new ADT Queue implementations in both attempts should account for any size and any data item type, thus you are required to utilize templates. Moreover, you are required to implement all data validations needed and handle/report errors whenever needed.

Finally, You are required to analyze the new Queue ADT, in both attempts, using the Big-O notation for the new Queue ADT operations, precisely the enqueue and

dequeue. Moreover, you need to show that your second attempt results in a better running time than the first one.