We want to implement a new data type: it takes a number N, and allows us to insert exactly N items.

Then, we can retrieve items from it one by one, but the order it gives the items out is by always returning the middle element with respect to the insertion order.

For example, if we say N = 6 and we insert 1, 2, 3, 4, 5, 6, the first item we get when we call retrieve will be 3, then 4, then 2, then 5, then 1, and lastly 6.

How can we implement this data type using only stacks and queues? Explain how the insert and retrieve operations should work.

• Assume N is a positive integer, and that we always have to call insert exactly N times and add all the items, before we start retrieving them.
• Assume you can create any number of stacks and queues you'd like, but you don't have access to the arrays storing the data in the stacks/queues.