Question $5.[15$ points$]$

Efficient Ticketing System Using Dual Stack Strategy

Scenario:

Imagine a busy train station with a unique ticketing system. This system allows passengers to both purchase tickets and return them for cancellations. To manage this effectively, the station decides to implement a Double$-$Ended Queue $($Deque$)$ for ticket handling. However, due to limited system resources, they can only use two stacks to create this Deque.

Assignment Task:

$1.$ System Design: $(6$ points$)$

$$ Propose a method to construct a Deque for the train station$$s ticketing system using only two Stack instances. $(3$points$)$

$$ Describe how you would enable the system to add $($purchase$)$ and remove $($cancel$)$ tickets at both ends of the Deque using these stacks. Also, how to check if the Deque is empty and is the size of the Deque. $(3$ points$)$

$2.$ Real$-$World Application Analysis: $(6$ points$)$

$$ Analyze the time complexity of each operation in your Deque implementation.$(2$ points$)$

$$ What would be the worst time complexity and in which scenario $?(4$ points$)$

$3.$ Practical Considerations: $(3$ points$)$

$$ Discuss any potential challenges this system might face in a real$-$world setting. $(2$ points$)$

$$ Suggest possible improvements or alternative approaches to enhance the system's performance and reliability. $(1$ point$)$

Note: You do not need to give the java implementation for the stacks or the dequeue. A detailed description with a pseudo code is enough.

Remember, you can$$t use anything other than two stacks, no extra arrays, or queues for example. Of course, you are allowed to use variables to be able to return the values of the

operations for example.