Implement Queue using Two Stacks

Create a queue by using two stacks. First, write an approach where both enqueue and dequeue take O(n) time. Next, optimize the design so that enqueue and dequeue each run in O(1) time. Implement a class TwoStackQueue with an enqueue(int value) method and a dequeue() method that returns the next queued integer. For each input, the first line is the number of operations. Each following line is either push or pop. Output one line for each pop, containing the dequeued value.…