225. Implement stack with queue
Title Link: 225. Implement stack with queue (simple)
Title Description
Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).
Implement MyStack class:

void push(int x) pushes element X to the top of the stack.

int pop() removes and returns the top of stack element.

int top() returns the stack top element.

boolean empty() returns true if the stack is empty; Otherwise, false is returned.
be careful:

You can only use the basic operations of the queue  that is, push to back, peek/pop from front, size and is empty.

Your language may not support queues. You can use list or deque to simulate a queue, as long as it is a standard queue operation.
Example:
Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // Return 2
myStack.pop(); // Return 2
myStack.empty(); // Return False
Tips:

1 <= x <= 9

Call push, pop, top, and empty up to 100 times

Ensure that the stack is not empty every time pop and top are called
Problem solution
Idea: according to the meaning of the topic, use a common queue and a queue for backing up data (in fact, using a queue for this topic is enough).
Two queues are used: for push(), just push the elements into the normal queue one by one; For pop(), first pop up the first n1 elements in the ordinary queue (assuming there are n elements in the ordinary queue) and push them into the backup queue, and then pop up the last element; For top(), just return the end of line element; For empty(), you only need to judge whether the normal queue is empty.
Using a queue: push(), top(), empty() is the same as "using two queues"; for pop(), first pop up the first n1 elements in the queue (assuming there are n elements in the queue) in order, push them from the end of the queue, and then pop up the last element.
Code (C + +)
//Use two queues class MyStack { public: deque<int> deq1;//Normal queue deque<int> deq2;//Backup queue MyStack() { } void push(int x) { deq1.push_back(x); } int pop() { //If queue 1 is not empty, the first in the queue is deleted n1 Elements(Suppose there are n element)Push queue 2 and pop the last element while (deq1.size()  1 > 0) { deq2.push_back(deq1.front()); deq1.pop_front(); } int result = deq1.front(); deq1.pop_front(); //Push all the elements in queue 2 into queue 1 while (deq2.size() > 0) { deq1.push_back(deq2.front()); deq2.pop_front(); } return result; } int top() { return deq1.back(); } bool empty() { if (deq1.empty()) return true; else return false; } };
analysis:

Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

Spatial complexity: O(N), two queues are required.
//Use a queue class MyStack { public: deque<int> deq; MyStack() { } void push (int x) { deq.push_back(x); } int pop() { int size = deq.size(); while (size  1 > 0) { deq.push_back(deq.front()); deq.pop_front(); size; } int result = deq.front(); deq.pop_front(); return result; } int top() { return deq.back(); } bool empty() { return deq.empty(); } };
analysis:

Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

Spatial complexity: O(N), a queue is required.