Formatted question description: https://leetcode.ca/all/232.html
232 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. Example: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false Notes: You must use only standard operations of a stack -- which means only operations are valid push to top, peek/pop from top, size, and is empty Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). @tag-stack
As long as the element is inserted from the front every time, for example, if a queue is 1, 2, 3, 4, then we save it in the stack as 4, 3, 2, 1, and then return to the top element 1, also It is the first element of the queue.
The difficulty of this question is the push function. We need an auxiliary stack tmp, and store the elements of s into tmp in reverse order. At this time, add a new element x, and then store the elements in tmp back. This is the order we want , The other three operations also directly call stack operations.
To optimize above, because every time you push, you have to flip both stacks,
So, have stacks new and old, the new pushed elements are cached in _new first, and all elements in _new are moved to _old only when the operations are pop and peek, which improves efficiency.