Programming Skills: Implement Stack using Queues

[Problem]
https://leetcode.com/problems/implement-stack-using-queues/description/

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

You must use only standard operations of a queue -- which means only push_to_back, pop_from_front, size and is_empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

翻譯翻譯:
用queue來實做一個stack。請注意上述Note有要求，不論你是用stl的queue，或是自己寫queue，都只能使用queue基礎的push to back，pop from front, size, empty這幾個API。

[Solution]

Move away the 'existing item' between 'incoming item' and the 'Exit'.

Stack is a "Last In First Out" structure, which means we want incoming item being put on the place which is closest to the 'Exit'.
But in "Queue", there are a lots of things between the 'incoming item' and the 'Exit'.
e.g.
Exit <-- 1 <-- 5(incoming item)
'1' is in between.
To put the incoming item close to the 'Exit', we have to move obstacle '1' away.
Move to where?
1.We introduce one more queue(q2), then we can clear q1 by move those obstacles into q2.
2.We put incoming item to q1 which is empty, so it is close to 'Exit'.
3.We put those things in q2 back to q1.
If we do step1,2,3 when we push any item. The "Last In First Out" can be achieve .
e.g.
push(1)
q1:1
q2:

push(5)
q1: q1:5 q1:51
q2:1 q2:1 q2:

push(2)
q1: q1:2 q1:251
q2:51 q2:51 q2:

pop() get 2
q1:251 q1:51

pop() get 5

q1:51 q1:1

pop() get 1
q1:1 q1:

Note: The key point is to move away those obstacles. But you can choose when to move.
You can move them when Push() or Pop(). There it a detail explanation of each approach.
https://leetcode.com/articles/implement-stack-using-queues/

[Advance Solution]
In previous solution, to swap the position of 'incoming item' and 'existing item', we introduce queue2 as a temporary storage.
But we can achieve the swapping by using only queue1.
If you pop front item and push it back, then the swapping is achieved.
e.g.
q1:51 pop_front q1:1 push_back(5) q1:15
'1' and '5' are swapped.
This is true even there are many existing items.
e.g.
q1:1234 (pop_front & push_back)x3 times q1:4123
'123' and '4' are swapped.

Let's implement this idea


class MyStack {
public:

    queue<int> q;
    
    void push(int x) {
        q.push(x);
        for(int i=0;i<q.size()-1;i++){
            q.push(q.front()); 
            q.pop();
        }
    }
    
    int pop() {
        int res=q.front(); q.pop();
        return res;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};