Requirements

Functional Requirements:

• Stack supports push(item), pop(), and peek() operations in LIFO order.
• Queue supports enqueue(item), dequeue(), and peek() operations in FIFO order.
• Track size and support isEmpty() check for both stack and queue.
• Support generic element types for both Stack and Queue.

Non-Functional Requirements:

• extensability of features should be possible in give data structures
• code should be extendable to introduce more data structures in future
• reusability
• time

Core Objects & Relationships

Based on the requirements and use cases, identify the main objects of the system and analyze how they interact and relate to each other...

Node data structure which will hold the element data based on customers requested element type using polymorphism

DataStructureManager will maintain LinkedList that will be collection of Nodes

DataStructureImplementationInterface will have common methods size and isEmpty

Stack and Queue classes will be derived from DataStructureImplementationInterface and have their own implementations of size(), isEmpty() and their own properties for stack push, pop, peek based on LIFO

and queue enqueue, dequeue, peek based on FIFO

for optimal implementations we'll maintain both heads and tails

I prefer to use LinkedList over arrays for memory optimisation especially in case of queue in case of array, removing first element will need whole array to be shifted by 1 element that would cause O(n) time complexity , while for LinkedList we just need to remove first node and update head

so we will use doubly linked list for efficient removal of element from tail.

and if in array we don't remove the first element by shifting elements and maintain a head pointer then at some point we may face out of memory because the unncecessary space is not getting freed up

in case of stack though getting and removing last element but to add element we need to predefine the size of array else extending the memory would cause time complexity to increase and code also complex.

vector could be used for stack but it would be unnecessary to use different data structures and for better reusability and simpler code it is better to return LinkedList

APIs & Class Members

Node: this class will act is the basic building unit of linked list that will be used to implement stacks and queues

DSManager: this class will use node to create linked list streets head and tail basically this class will maintain the states of data structures stacks and queues. Apart from this it will contain reusable methods that will be used to implement the functionalities of data structures

It will also contain mutex attribute that will be used to implement locks and avoid race conditions during concurrent conditions

IDS: this will act as abstract class, containing common methods like size and isEmpty that will be used by all its child classes

stack class: it will be derived from IDS and contain the implementation of methods pop, push, peek, size and isEmpty using the reusable methods defined in DSManager

and queue class: it will be derived from IDS and contain the implementation of methods like enqueue, dequeue, peek, size and isEmpty using the reusable methods defined in DSManager

Deep Dive

Explain design tradeoffs you considered. Check and explain whether your design adheres to SOLID principles. Explain how your design can handle changes in scale and whether it would be easy to extend with new functionalities. Identify areas for future improvement...

SOLID:

Single responsibility: DS is only responsible for maintaining data structure state, while stack and queue classes are only responsible for core methods

Interface segmentation, only common methods of stack and queue are defined in IDS

Open for extension close for modification, in future if we want to introduce a new data structure we just need to define a separate concrete class derived from IDS without touching other concrete data structure implementations

for example in future if we also want to introduce priority_queue we can independently create another concrete class derived from IDS with its own implementation using DSManager methods without touching stack and queue class implementations

Liskov Substitution: derived classes stack and queue inherit all properties of parent (size, isEmpty) and are well defined along with their own methods defined for push , pop, peek, queue dequeue based on LIFO and FIFO respectively

exceptions are returned in case of nullptr scenarios , eg. when we try to remove element from stack or queue when empty or trying to get top or front elements respectively when stack and queue are empty

additional considerations taken in this design is to add locking using mutex to avoid race conditions

now if we have multiple threads trying to access same stack or queue unless the tasks of thread1 is complete, all methods will remain locked and inaccessible unless thread1 task is complete hence it will help tackle race conditions and avoid returning inaccurate data to any user.

part from this corner cases like throwing exceptions when trying to pop/dequeue or get peek element when stack / queue is empty making the implementation more robust

while we scale, then locking may lead to increased latency as other threads won't be able to access the stack/queue unless one thread tasks are done

so to increase throughput in future lock free implementation using CAS (Compare and Swap)can be used which will ensure atomic updates while not locking the stack till complete task completion