Linguini has just started his job as a plongeur at the famous restaurant, Gusteau’s. He wants to make a good first impression and decides to clean the dishes in the order that they are given to him. The problem is that to save space in the kitchen, the dishes must be placed in two stacks! How could you implement the methods of a queue using only these two stacks to help Linguini?
Remember, stacks work in a Last In First Out (LIFO) order, meaning the last element that was pushed will be the first element to be popped.
Conversely, a queue works in First In First Out (FIFO) order, meaning the first element enqueued will be the first element to be dequeued.
If you need a refresher on this material, take a look at the lecture slides from CS15 on stacks and queues.
Your task: Write pseudocode for the following methods of a queue: enqueue(value) and dequeue(). The dequeue() method should return the element being removed from the queue. Assume you have instance variables s1 and s2 that represent the two stacks, which already have the methods push(value), pop() (which returns the top element), and isEmpty() (which returns a boolean). You may call these methods freely on both stacks, and can assume that they will function as per the standard stack definition described above. You can assume that the pop() method handles returning an element in the case that the stacks are empty (i.e. calling pop() on an empty stack will return null). You may not use any other data structures to store your data (like arrays or ArrayLists).